# HG changeset patch # User Masataka Kohagura # Date 1398082536 -32400 # Node ID 5bdd06f52b6197fa3293a021436274778321e118 # Parent 6e9ee8c1f3033635c30db15cab272490d7d6190c add expriment Data diff -r 6e9ee8c1f303 -r 5bdd06f52b61 experiment.txt --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/experiment.txt Mon Apr 21 21:15:36 2014 +0900 @@ -0,0 +1,65 @@ +2014/04/18 (Fri) + [memo] + word count の再計測 + + ./word_count -file 1gb.txt -cpu 12 -division 128 -block 48 -m + (CPU num = 12) + < mmap > 22.713 0.878 + < read > 12.520 1.469 + < bread & IO_0 > 10.295 0.886 + < bread & SPE_ANY > 14.028 0.882 + + (CPU num = 8) + < mmap > 22.789 0.952 + < read > 14.785 1.571 + < bread & IO_0 > 14.774 0.857 + < bread & SPE_ANY > 15.287 1.009 + + (CPU num = 4) + < mmap > 22.861 1.739 + < read > 15.737 2.303 + < bread & IO_0 > 14.634 1.565 + < bread & SPE_ANY > 15.646 1.941 + + (CPU num = 1) + < mmap > 20.179 6.521 + < read > 21.351 6.832 + < bread & IO_0 > 13.930 6.009 + < bread & IO_0 > 18.531 6.775 + + + + ./word_count -file X gb.txt -cpu 12 -division 128 -block 48 -m + (file size 2GB) + < mmap > 38.208 + < read > + < bread & IO_0 > 24.201 + < bread & SPE_ANY > 28.411 + + (file size 3GB) + < mmap > 58.514 2.290 + < read > + < bread & IO_0 > 36.397 + < bread & SPE_ANY > 41.740 + + (file size 4GB) + < mmap > 73.767 + < read > + < bread & IO_0 > 47.967 + < bread & SPE_ANY > 53.813 + + + + + ./word_count -file 1gb.txt -cpu 12 -division 16 -block 48 -m + < mmap > 11.137 0.854 + < read > 11.437 1.487 + < bread & IO_0 > 11.412 0.847 + < bread & SPE_ANY > 11.146 0.866 + + ./word_count -file 1gb.txt -cpu 1 -division 16 -block 48 -m + < mmap > 17.421 6.739 + < read > 19.285 7.037 + < bread & IO_0 > + < bread & SPE_ANY > + diff -r 6e9ee8c1f303 -r 5bdd06f52b61 paper/cerium.tex --- a/paper/cerium.tex Mon Apr 21 14:53:36 2014 +0900 +++ b/paper/cerium.tex Mon Apr 21 21:15:36 2014 +0900 @@ -1,7 +1,8 @@ \section{Cerium TaskManager}\label{section:cerium} Cerium Task Manager は並列プログラミングフレームワークであり、内部では C や C++ で実装されている。 -Cerium Task Manager は、User が並列処理を Task 単位で記述し、関数やサブルーチンを Task として扱い、その Task に対して Input Data、Output Data 及び依存関係を設定する。 +Cerium Task Manager は、User が並列処理を Task 単位で記述し、関数やサブルーチンを Task として扱い、その Task に対して Input Data、Output Data を設定する。 +Input Data、Output Data とは関数でいう引数に相当する。そして Task が複数存在する場合、それらに依存関係を設定することができる。 そして、それに基づいた設定の元で Task Manager にて管理し実行される。 Cerium Task Manager は PlayStation 3/Cell、Mac OS X 及び Linux 上で利用することが可能である。 @@ -63,9 +64,10 @@ \end{center} \end{table} \end{tiny} +set\_inData には、WordCount Task が担当するテキストの範囲を設定し、set\_outData にはその範囲の単語数や行数、範囲の先頭と末尾の状態を表すフラグを配列として格納してる。 +input data は分割されたデータが送られてくるため、分割された前後のテキストがどうなっているかはわからない。 +そのため、担当範囲であるデータの先頭と末尾のパラメータを単語数と行数の他に付け加える。後にそのデータを他の WordCount の結果と照らし合わせ、分割されたテキストを正しく整合する。 -しかし、input data は分割されたデータが送られてくるため、分割された前後のテキストがどうなっているかはわからない。 -そのため担当範囲であるデータの先頭と末尾のパラメータを単語数と行数の他に付け加える。後にそのデータを他の WordCount の結果と照らし合わせ、分割されたテキストを正しく整合する。 Task の記述は以下のようになる。 \\ @@ -129,7 +131,8 @@ \end{tiny} Print Task は WordCount Task によって書き出された単語数と行数を集計し、結果を出力する Task である。 -WordCount Task が全て走り終わったあとに、Print Task が走るように wait をかけている。(図\ref{fig:wordcount}) +WordCount Task が全て走り終わったあとに、Print Task が走るように依存関係を設定している。(図\ref{fig:wordcount}) + \begin{figure}[htbp] \begin{center} @@ -139,6 +142,7 @@ \label{fig:wordcount} \end{figure} +\if0 単語数や行数、そして担当範囲の先頭と末尾の文字列の状態を配列としてデータを保持している。 その配列を Print Task にて処理を行い単語数、行数を集計する。 @@ -180,3 +184,4 @@ return 0; } \end{verbatim} +\fi diff -r 6e9ee8c1f303 -r 5bdd06f52b61 paper/io.tex --- a/paper/io.tex Mon Apr 21 14:53:36 2014 +0900 +++ b/paper/io.tex Mon Apr 21 21:15:36 2014 +0900 @@ -1,11 +1,14 @@ \section{並列処理向け I/O の設計と実装} -従来は mmap や read でファイルの読み込みの実装を行っていた。 +従来は mmap でファイルの読み込みの実装を行っていた。 mmap とは、sys/mman.h に含まれている関数で、ファイルの読み込み等に使用される関数である。 -ユーザ(プロセスの)メモリ空間にファイルのマッピングを行う UNIX のシステムコールであり、 +ユーザ +%(プロセスの) +メモリ空間にファイルのマッピングを行う UNIX のシステムコールであり、 mmapした領域にアクセスされるときに、そのファイルが実メモリに展開される。 +\if0 \begin{tiny} \begin{table}[ht] \begin{center} @@ -33,6 +36,7 @@ \end{center} \end{table} \end{tiny} +\fi \if0 ファイルディスクリプタで指定したファイルを offset から len バイトの範囲を読み込む。 @@ -41,17 +45,18 @@ flags にはメモリ確保する際のオプションを指定することができる。(表\ref{table:mmap}) \fi -mmap でファイルを読み込むタイミングは、mmap 関数が呼ばれたときではなく、mmap した領域に対して何らかのアクセスをしたときに初めてファイルが読み込まれる。 +% mmap でファイルを読み込むタイミングは、mmap 関数が呼ばれたときではなく、mmap した領域に対して何らかのアクセスをしたときに初めてファイルが読み込まれる。 + -図\ref{fig:mmap}では、読み込んだファイルを分割して、それらの領域に何らかの処理を加えるときの図である。 +図\ref{fig:mmap}では、mmap で読み込んだファイルを分割して、それらの領域に何らかの処理を加えるときの図である。 -1個目の Task が実行されるときに初めてそれらの領域にファイルが読み込まれ、その後何らかの処理が行われ、そして Task 2 も同様に読み込みを行ってから処理が行われる。 +1個目の Task が実行されるときに初めてそれらの領域にファイルが読み込まれ、その後 WordCount が行われる。 +そして Task 2 も同様に読み込みを行ってから WordCount が行われる。 これら Task は並列に実行されるべきであるが、ファイル読み込みの I/O 部分がネックとなり、本来並列実行される Task が読み込み待ちを起こしてしまう恐れがある。 さらに、読み込みが OS 依存となるために環境によって左右されやすく、プログラムの書き手が読み込みに関して制御しにくい。 それらを解決するためには、ファイル読み込みと Task を分離し、ファイルの読み込みも制御できるようになれば高速で動くのではないかと考えた。 - \begin{figure}[htbp] \begin{center} \includegraphics[scale=0.5]{images/mmap.pdf} @@ -63,10 +68,10 @@ \subsection{Blocked Read の設計と実装} -Blocked Read とは、読み込みの Task と、それらに対して何らかの処理を行う Task を切り離すための実装方法である。それを実現するため、pread 関数にて実装した。 +Blocked Read とは、読み込みの Task と、WordCount を切り離すための実装方法である。それを実現するため、pread 関数にて実装した。 pread 関数は、unistd.h に含まれている UNIX 専用の関数である。 ファイルディスクリプタで指定したファイルの先頭から offset 分ずれた場所を基準として、その基準から count バイトを読み込み、それを buf に格納する。 -(表4) +(表\ref{table:pread}) \begin{tiny} \begin{table}[ht] @@ -92,22 +97,22 @@ \end{tiny} 従来の実装との違いは、ファイルの読み込みがどのタイミングで起こるかである。 -Blocked Readは、読み込み専用の Read Task と、処理専用の Task を別々に生成する。 +Blocked Readは、読み込み専用の Read Task と、WordCount を別々に生成する。 Read Task はファイル全体を一度に読み込むのではなく、ある程度の大きさで分割を行ってから読み込む。 -分割して読み込み終わったら、読み込んだ範囲内の Task が実行される。 -%(図\ref{fig:block}) -(図4) -Read Task が生成されて、その後 Task の生成となるので、Read Task は常に走っている必要がある。 +分割して読み込み終わったら、読み込んだ範囲内の WordCount が実行される。 +(図\ref{fig:block}) + +Read Task が生成されて、その後 WordCount Task の実行となるので、Read Task は連続で走っている必要がある。 \begin{figure}[htbp] \begin{center} \includegraphics[scale=0.4]{images/blockedreadimage.pdf} \end{center} -\caption{Read Task と 処理 Task の分離} +\caption{Read Task と WordCount の分離} \label{fig:block} \end{figure} -この図では、Read Task 1つに対して Task 1つ起動しているが、このように1つ1つ生成、起動をすると Task 生成でメモリを圧迫してしまい、全体的な動作に影響を与えてしまう。 +この図では、Read Task 1つに対して WordCount を1つ起動しているが、このように1つ1つ生成、起動をすると Task 生成でメモリを圧迫してしまい、全体的な動作に影響を与えてしまう。 実際には Task をある一定数まとめた単位で生成し、起動を行っている。この単位を Task Block と定義する。 Task Block 1つ当たりがの Task 量を $n$ とおく。Task 1つ当たりの読み込む量を $L$ とすると、Task Block 1つ当たりの読み込む量は $L \times n$ となる。 @@ -148,11 +153,10 @@ \end{verbatim} set\_cpu にて Read Task を担当するデバイスの設定を行う。 -set\_outData(0) にファイルを読み込んだときの格納場所を指定し、set\_param(0) にて読み込むファイルのファイルディスクリプタを設定している。 +set\_outData(0) にファイルを読み込んだときの格納場所を指定し、set\_param(0) にて読み込むファイルディスクリプタを設定している。 set\_param(1) 、 set\_param(2) にて Blocked Read Task 単体で読み込むファイルの範囲の先頭と末尾のポジションを設定する。 -なお、run\_tasks 内部で、処理を行う task を生成している。 -その内部で、task が生成されるたびに task\_num のインクリメントを行っている。 +なお、run\_tasks 内部で、task が生成されるたびに task\_num のインクリメントを行っている。 Blocked Read Task の記述は以下のようになる。 @@ -210,14 +214,15 @@ %\end{figure} IO\_0 は、SPE\_ANY よりも priority を高く設定しているので、IO\_0 で設定された Read Task に SPE\_ANY で設定した 文字列検索 Task に割り込まれることがなくなる。 -Cerium では、並列処理を pthread で記述しており、pthread\_getschedparam()でIO\_0 の priority を設定している。 -pthread\_getschedparam は、〜をする関数である。 +Cerium では、並列処理を pthread で記述しており、pthread\_getschedparam()でIO\_0 の priority を設定することができる。 (図\ref{fig:io0}) \begin{figure}[htbp] \begin{center} -\includegraphics[scale=0.35]{images/io0.pdf} +\includegraphics[scale=0.3]{images/io0.pdf} \end{center} \caption{Blocked Read Task を IO\_0 での実装時} \label{fig:io0} \end{figure} + +\newpage diff -r 6e9ee8c1f303 -r 5bdd06f52b61 paper/sigos.pdf Binary file paper/sigos.pdf has changed