\documentclass[10pt]{jsarticle}
\usepackage{/home/haraken/tex/style/report}
\title{DMIの性能評価と今後の方向性}
\author{はらけん}
\date{\mytoday}

\begin{document}

\maketitle

\section{DMIが対象とする分散処理}
\label{sec:target}

DMIの最大の目的はノードの動的な参加/脱退のサポートであるため，
ノードの動的な参加/脱退に相応して動的に並列度が増加/減少する処理でなければ，わざわざノードを参加/脱退させる意味がない．
よって，DMIが対象とすべき分散処理は，
数台程度までしかスケールしないような処理ではなく，
ある程度のスケーラビリティを発揮できる処理である．
したがって，DMIは，細粒度なデータアクセスが頻繁に干渉するような処理ではなく，
データアクセスがある程度粗粒度でアクセス干渉の少ないような処理を対象として設計する．
当然，このようにデータアクセスが粗粒度で干渉の少ない処理は，
分散共有メモリにおけるプログラミングの容易さを持ち出さずとも，
メッセージパッシングで十分記述できる場合が多い．
しかし，それにも関わらず\textbf{本研究があえて分散共有メモリをベースとする理由は，
分散共有メモリではデータの送受信が仮想共有メモリへのアクセスに抽象化されるため
ノードの参加/脱退を容易に記述できるからである}，という点を強調したい．

\section{DMIのシステム概要（何を性能評価したのか）}

スライド参照．

\section{DMIの性能評価}

\subsection{概要}

\ref{sec:perform_read}ではDMIにおけるread操作のオーバーヘッドを，
\ref{sec:perform_multi}ではマルチモードread/writeの有効性を，
\ref{sec:perform_swap}では遠隔スワップシステムとしての性能と非同期read/writeの有効性を，
\ref{sec:perform_jacobi}，\ref{sec:perform_ep}，\ref{sec:perform_cg}では
各種アプリケーションに対するDMIとMPIとの性能比較およびノードの動的な参加/脱退を行うことの有効性を，
\ref{sec:perform_mm}では任意のページサイズを設定できることの有効性を検証する．
\ref{sec:perform_nas}では，NAS Parallel Benchmarkに対する文句をまとめる．
なお，DMIが採用するSequential ConsistencyやSingle Writer型のコンシステンシプロトコルは，
既存の緩和型コンシステンシモデルやMultiple Writer型のコンシステンシプロトコルよりも並列性が絞られるため，
データアクセスの競合が頻発する処理に対しては性能上不利になると考えられるが，これに関する評価は行えていない．
ただし，前述のように，そのような処理の多くは台数効果が出にくくノードの参加/脱退による効果が期待できないため，
DMIが主に対象とする処理ではない．

その他，DMIの特性を分析するために，ぜひ取得すべきデータがあれば教えてください．

\subsection{実験環境}

実験環境としては，kyutechの16ノードを用いた．
具体的な構成は，Intel Xeon E5410 2.33GHz（4コア）$\times$2のCPU，32GBのメモリ，
カーネル2.6.18-6-amd64のLinuxで構成されるマシン16ノードを1Gbitイーサネット$\times$2でネットワーク接続した，
合計128プロセッサのクラスタ環境である．
以降の実験では，DMI/MPIを$n$プロセッサで実行する際には，
8本のDMIスレッド/MPIプロセスを$\lfloor n/8\rfloor$台のノードに立て，
残りの$n-8\times\lfloor n/8\rfloor$本のDMIスレッド/MPIプロセスを別の1つのノードに立てるプロセス構成とした．
また，コンパイラにはgcc 4.1.2，MPIにはOpenMPI 1.3.3，最適化オプションには-O3を使用した．

\subsection{マイクロベンチマーク}

\subsubsection{read操作の性能}
\label{sec:perform_read}

\begin{figure}
  \centering
  \includegraphics[scale=0.6]{data_access.eps}
  \caption{データサイズを変化させたときの
    ローカルread（localread），リモートread（remoteread），memcpy（memcpy），
    データ転送（transfer）の実行時間．}
  \label{fig:data_read}
\end{figure}

\begin{figure}
  \centering
  \includegraphics[scale=0.6]{data_localread.eps}
  \caption{データサイズを変化させたときのローカルreadの内訳．}
  \label{fig:data_localread}
\end{figure}

\begin{figure}
  \centering
  \includegraphics[scale=0.6]{data_remoteread.eps}
  \caption{データサイズを変化させたときのリモートreadの内訳．}
  \label{fig:data_remoteread}
\end{figure}

DMIにおけるreadのオーバーヘッドを評価した．
DMIにおけるreadには，そのノードがすでにキャッシュを保有していてローカルに完了する場合（ローカルread）と，
オーナーに対してreadフォルトを送信して最新ページの転送を要求する場合（リモートread）の2種類がある．
ローカルreadの処理の内訳は，
DMI物理メモリのメモリ空間からユーザプログラムのメモリ空間へのmemcpyと，
ユーザレベルによるコンシステンシ管理などの処理系のオーバーヘッドである．
一方，リモートreadの処理の内訳は，
オーナーからのページ転送と，memcpyと，処理系のオーバーヘッドである．
なお，DMIのread/writeには，
複数ページにまたがってもよく，いかなるタイミングで呼び出しても安全に処理される
\texttt{DMI\_read(...)}/\texttt{DMI\_write(...)}と，
単一ページにしかアクセスできず，
良からぬタイミング（たとえばメモリ解放中など）で呼び出すとシステムが未定義状態に陥る可能性がある一方で
高速に実行可能な\texttt{DMI\_oneread(...)}/\texttt{DMI\_onewrite(...)}が存在する．
これらの実行速度としては，8バイトのローカルreadに関して，
\texttt{DMI\_oneread(...)}は\texttt{DMI\_read(...)}よりも約20倍高速だった．
以下の実験は，\texttt{DMI\_oneread(...)}を用いて行ったものである．

\figref{fig:data_read}には，さまざまなデータサイズ$x$に関して，
ページサイズ$x$のページ1個をローカルreadするのに要する時間，
およびリモートreadするのに要する時間，サイズ$x$のデータのmemcpyに要する時間，
サイズ$x$のデータの転送に要する時間を比較した結果を示す．
また，ページサイズを変化させたときに，
ローカルread全体の実行時間に占めるmemcpyの比率およびオーバーヘッドの比率を\figref{fig:data_localread}に，
リモートread全体の実行時間に占めるページ転送の比率，memcpyの比率，
およびオーバーヘッドの比率を\figref{fig:data_remoteread}に示す．
なお，これらのグラフには100回測定した場合の平均値をプロットしているが，
1KB以下の場合のmemcpyやページ転送はあまりに高速過ぎるため，
測定ごとのばらつきが非常に大きく，正確な数値を読み取ることにはあまり意味がない．

\figref{fig:data_read}より，
リモートreadはローカルreadよりも，2MB以上では9.52倍〜9.96倍遅く，
10KB以下では50.8倍〜81.4倍遅いことがわかる．
ローカルreadに関して\figref{fig:data_localread}の内訳を見ると，
500KB以上では処理系のオーバーヘッドが占める比率が1\%以下となるものの，
100バイト以下では80\%以上を占めることがわかる．
しかし，ローカルreadでは，
（1）ページテーブルから該当ページの管理情報を取り出し，
（2）そのページに対する他の操作を排他し，
（3）アクセスチェックを行い，
（4）memcpyし，
（5）排他を解除するという操作を行うのみであり，
これらはユーザレベルでコンシステンシ管理を行う以上は最低限必要になる操作であるため，やむを得ない．
また，リモートreadに関して\figref{fig:data_remoteread}の内訳を見ると，
100KB以上ではオーバーヘッドの比率が15\%以下に抑えられるものの，2KB以下では50\%以上を占めており，
今後ネットワーク性能が向上すれば，さらにこの比率は増加すると予測される．
以上より，現状のDMIは細粒度なアクセスが頻発する処理には弱くオーバーヘッドの低減が重要な課題と言えるが，
最初に述べたように，そのような処理の多くは台数効果が出にくくノードの参加/脱退による効果が期待できないため，
DMIが主に対象とする処理ではない．


\subsubsection{マルチモードread/writeの性能}
\label{sec:perform_multi}

DMIでは，read/write/fetch-and-store/compare-and-swapをベースとした，
共有メモリベースのPermission Wordアルゴリズムに基づいて排他制御を実装している．
Permission Wordアルゴリズムをpthread型のインタフェースに従って書き換えたものを以下に示す：

\begin{code}
01: struct mutex_t {
02:   int *head;
03:   int *next;
04:   int *p1;
05:   int *p2;
06: };
07: 
08: void init(struct mutex_t *mutex) {
09:   mutex->head = NULL;
10:   mutex->next = NULL;
11:   mutex->p1 = NULL;
12:   mutex->p2 = NULL;
13: }
14: 
15: void lock(struct mutex_t *mutex) {
16:   int flag;
17:   int *prev, *curr;
18:   
19:   flag = 0;
20:   curr = convert(&flag, mutex->p1, mutex->p2);
                          /* address conversion */
21:   prev = fetch_and_store(&mutex->head, curr);
22:   if(prev == NULL) {
23:     mutex->p1 = curr;
24:   } else {
25:     while(flag == 0); /* spin */
26:   }
27:   mutex->next = prev;
28: }
29: 
30: void unlock(struct mutex_t *mutex) {
31:   int *curr;
32:   
33:   if(mutex->next == NULL 
         || mutex->next == mutex->p1) {
34:     if(mutex->next == mutex->p1) {
35:       mutex->p1 = mutex->p2;
36:     }
37:     if(!compare_and_swap(&mutex->head, mutex->p1, NULL)) {
38:       mutex->p2 = mutex->head;
39:       curr = revert(mutex->p2); /* address reversion */
40:       *curr = 1;
41:     }
42:   } else {
43:     curr = revert(mutex->next); /* address reversion */
44:     *curr = 1;
45:   }
46: }
47: 
48: void destroy(struct mutex_t *mutex) {
49: }
50: 
51: int* convert(int *curr, int *p, int *q) {
52:   int v1, v2, d;
53:   
54:   v1 = (intptr_t)p & 0x3;
55:   v2 = (intptr_t)q & 0x3;
56:   d = 0;
57:   if(d == v1 || d == v2) {
58:     d = 1;
59:     if(d == v1 || d == v2) {
60:       d = 2;
61:     }
62:   }
63:   return (int*)((intptr_t)curr + d);
64: }
65: 
66: int* revert(int *curr) {
67:   return (int*)((intptr_t)curr - ((intptr_t)curr & 0x3));
68: }
\end{code}

この実験では，上記の排他制御アルゴリズムを題材にして，マルチモードread/writeの有効性を評価した．
アルゴリズムの詳細は（あまりにややこしいので）理解する必要はないが，
重要なポイントだけ抑えておくと，
構造体\texttt{mutex\_t}のメンバ変数に対して，
23行目，27行目，35行目，38行目でwriteを，
21行目でfetch-and-storeを，37行目でcompare-and-swapを行い，
20行目の直前，33行目の直前，38行目の直前でreadを行っている．
そして，DMIではアクセス競合時の性能低下を防ぐために，
全てのwriteとfetch-and-storeとcompare-and-swapをWRITE\_REMOTEモードで，
全てのreadをREAD\_ONCEモードで行っている．
この理由は，writeなどをWRITE\_LOCALモードで行うと，
排他制御の度にオーナーが変化するため，
アクセス競合時にオーナーの頻繁な移動が発生してオーナー追跡のための通信が多量に発生するためである．
また，全てのreadをREAD\_ONCEモードで行う理由は，
アクセス競合時にはデータをreadしてから次にreadするまでの間に他ノードによってそのデータが更新される可能性が高いため，
READ\_INVALIDATEモードやREAD\_UPDATEモードによってデータをキャッシュすることに意味がない上に，
多量のinvalidate要求やupdate要求が発生してしまうためである．

以上のようなマルチモードread/writeの使い分けの効果を検証するため，
全てのwriteとfetch-and-storeとcompare-and-swapを$X$モードで，
全てのreadを$Y$モードで行う場合の性能を，
（\I）$X=$WRITE\_REMOTE，$Y=$READ\_ONCE，
（\II）$X=$WRITE\_LOCAL，$Y=$READ\_ONCE，
（\III）$X=$WRITE\_REMOTE，$Y=$READ\_INVALIDATE，
（\IV）$X=$WRITE\_REMOTE，$Y=$READ\_UPDATE，
の4通りに関して，
排他制御された1個のカウンタ変数を各DMIスレッドが300回インクリメントする処理を，
128DMIスレッドで行う処理の時間を測定した．
その結果，（\I）が44.97sec，（\II）が379.87sec，（\III）が53.11sec，（\IV）が70.74secとなった．
この結果より，オーナーの位置やキャッシュの状況などを意識してマルチモードread/writeを適切に使い分けることによって，
大きな性能向上を実現できる可能性があり，
マルチモードread/writeは分散共有メモリにおける有効な最適化手段であると言える．

このマルチモードread/writeは，
この排他制御の例のようにある限られた場面においてのみ効果が出るような最適化手段ではなく，
\textbf{かなり広い場面において実用的に有効な最適化手段}である．
論文の査読者からも，このマルチモードread/writeには一定の独自性があると思われるので，
もう少し強調してもいいのではないかというコメントをいただいた．

\subsubsection{非同期read/writeを利用する遠隔スワップシステムの性能}
\label{sec:perform_swap}

\begin{figure}
  \centering
  \includegraphics[scale=0.6]{data_stream.eps}
  \caption{HDDアクセスの実行時間，
    STREAMベンチマークにおける\texttt{DMI\_read(...)}/\texttt{DMI\_write(...)}の実行時間（DMI(sync)），
    非同期\texttt{DMI\_read(...)}/\texttt{DMI\_write(...)}の実行時間（DMI(async)）．}
  \label{fig:data_stream}
\end{figure}

STREAMベンチマークで採用されているcopy，scale，add，triaddの各処理に関して，
非同期read/writeを利用する遠隔スワップシステムの性能とHDDアクセスの性能を比較した．
STREAMベンチマークは，本来CPUのメモリバンド幅を測定するためのベンチマークであり，
キャッシュに乗り切らない程度に大きい3つの配列$A,B,C$と定数$d$を用意して，
copy（$C=A$），scale（$B=dC$），add（$C=A+B$），triadd（$A=B+dC$）の演算を行う時間を計測する．
つまり，主記憶への連続アクセスを通じて，CPUのbyte/flopsを求めるのがSTREAMベンチマークの目的である．

DMIの遠隔スワップシステムにおける評価では，16ノードを使用し，
各ノードが提供するDMI物理メモリ量を2GBに設定し，
3つの8GB配列$A,B,C$をページサイズ1MBでDMI仮想共有メモリ上に確保した．
そして，各配列$A,B,C$に関して，
先頭から$i\times512\mathrm{MB}$以上$(i+1)\times512\mathrm{MB}$未満$(0\le i<16)$の領域が，
ノード$i$にはオーナー権を伴ったDOWN\_VALID状態で存在し，
他のノードにはINVALID状態で存在するように配列領域を分散配置した上で，
配列$A$から配列$C$への8GBのcopyをノード0が逐次で行う実行時間を測定した．
同様にして，測定の度に前述の分散配置をやり直し，
ノード0が逐次でscale，add，triaddを行う実行時間を測定した．
この実験では，各配列のread操作にはREAD\_ONCEモードを，
各配列のwrite操作にはWRITE\_LOCALモードを使用した．
なお，各ノードが提供するDMI物理メモリ量を2GBに設定しているため，この処理では絶えずページの追い出し処理が発生する．

\figref{fig:data_stream}に，copy，scale，add，triaddの各処理を，
（\I）通常の\texttt{DMI\_read(...)}/\texttt{DMI\_write(...)}を利用して同期的に行った場合，
（\II）非同期read/writeを利用して，4MB先のプリフェッチおよび4MB後のポストストアを行った場合，
（\III）SATA 7200rpmのHDDへの初回アクセスで行った場合の性能を比較した結果を示す．
\figref{fig:data_stream}より，4つの処理を平均すると，
（\I）は（\III）より1.58倍高速で，（\II）は（\III）より2.00倍高速である．
この結果より，DMIが実現する大規模メモリがHDDよりも高速なストレージとして利用可能なこと，
および非同期read/writeが有効な最適化手段であることがわかる．

ただし，この非同期read/writeに関しては，
有効利用できる場面がそれほど多くないと思われる．
MPIの非同期send/recvにも言えることだが，
非同期操作は，計算と通信がちょうど良いバランスになるような処理でないとその効果が見えにくいため，
有効性が確認できるアプリが限られる．
事実，今回の性能評価で試した処理の中で，非同期操作の有効性が明らかに見えたのはこの実験だけである．

また，今のところ，既存の遠隔スワップシステムとの相対比較は行えていないが，
おそらく（というか間違いなく）既存の遠隔スワップシステムと比較するとDMIの性能は著しく低いと予想される．
その理由は主に2点ある．
第一の理由は，DMIのように，OSのメモリ保護機構を利用することなくユーザレベルで遠隔スワップを行うのは，
遠隔スワップの本来の目的とずれており，あまりに遅いからである．
遠隔スワップの本来の目的は，
ネットワークの高速化を背景として，
メモリ階層における主記憶とディスクスワップとの間に，遠隔メモリを挟み込むことにある．
よって，もっとも正道な遠隔スワップの実現方法は，
カーネルモジュールとしてデバイスを実装し，
アプリケーションからは完全に透過的に遠隔スワップを実現する方法である．
事実，AnemoneやNswapなど，性能を意識した遠隔スワップシステムではこのような実装を取るのが主流であり，
最近では，InfinibandやMyrinet環境での効率的な遠隔スワップの実装に関する研究が盛り上がっているようである．
これらの研究に対して，DLMは，
「わざわざデバイスを作ることなくユーザレベルで実装しても性能はあまり変わらない」という主張のもとで，
OSのメモリ保護機構を利用して実装しているが，評価結果を見る限り，やはり遅い印象がある
（相対評価を行っていないので実際のところはよくわからない）．
いずれにせよ，遠隔スワップはこういうレベルで論じられるべき話なので，
DMIのようにユーザレベルでごちゃごちゃ行うような実装では，性能面ではまず対抗できない．
第二の理由は，遠隔スワップシステムでは，
高性能な大規模メモリの提供が最大の焦点であるため，主に逐次プログラムの実行が対象とされる．
つまり，逐次プログラムに特化することにより，
分散共有メモリのような複雑なコンシステンシ管理を一切排除し，
プロトコルを単純化することで効率化が図られている．
よって，分散共有メモリの実現を主目的とするDMIにおける遠隔スワップシステムが，
それら逐次プログラム用に最適化された遠隔スワップシステムと比較して遅いのはやむを得ない
（当然，DMIでは並列実行環境が提供されるので，
処理を並列化することで「全体として見れば」性能向上できるような場面はあるのかもしれないが，
少なくとも遠隔スワップシステムとしてのread/write速度では太刀打ちできない）．
分散共有メモリに遠隔スワップシステムの機能を付加させた既存研究には，
JIAJIAやCashmere-VLMなどがあるが，
これらの研究も遠隔スワップシステムとしてのread/writeの性能を競っているわけではなく，
分散共有メモリ$+$遠隔スワップシステムという処理系が実現できたことを強調している．
以上を踏まえると，DMIにおける遠隔スワップシステムは，
JIAJIAやCashmere-VLMなどの既存研究の二の舞に過ぎず，
性能面で有利なアプローチも特に入れていないため，
これ以上踏み込まない方が無難だと考えている．

\subsection{アプリケーションベンチマーク}

以降の実験で使用するDMIプログラムは全て，
pthreadで記述したプログラムに対して，ほぼ機械的な変換作業を手動で施す形で作成した．

\subsubsection{ヤコビ反復法による3次元熱伝導方程式の求解}
\label{sec:perform_jacobi}

この実験はHimenoベンチマークを都合よく改造したものである．

3次元熱伝導方程式をヤコビ反復法で解く処理を題材にして，
ノードの動的な参加/脱退に伴って並列度を動的に変化させる効果を評価した．
$n=512$として，$1\le x\le n,1\le y\le n,1\le z\le n$の各格子点を要素とする立方体の物体を考え，
初期状態として，$y=1$の面の要素に$T_0(x,1,z)=1$の温度を与えて，その他の要素の温度は$T_0(x,y,z)=0$とした．
ヤコビ反復法の第$i$イテレーションでは全ての要素$(x,y,z)$に関して，
$$
T_i(x,y,z)=(T_{i-1}(x-1,y,z)+T_{i-1}(x,y-1,z)+T_{i-1}(x,y,z-1)
+T_{i-1}(x+1,y,z)+T_{i-1}(x,y+1,z)+T_{i-1}(x,y,z+1))/6
$$
の更新を行い，
$\sum_{x=1}^n\sum_{y=1}^n\sum_{z=1}^n|T_i(x,y,z)-T_{i-1}(x,y,z)|/n^3<10^{-5}$
を満たすまでイテレーションを繰り返した．
DMIでは，各イテレーションの先頭でノードの参加/脱退を処理し，
その時点で参加しているノードたちで$z$軸方向に領域を均等に分割して，そのイテレーションを実行するようなプログラムを記述した．
各イテレーションでは，各プロセッサが自分の担当領域の境界面の温度を計算する際に，
直前のイテレーションで隣のプロセッサが更新した領域を参照する必要が生じるため，
この境界面が1ページになるようにページサイズを設定した．
また，自分の担当領域の更新にはWRITE\_LOCALモードを利用し，
境界面の計算時に直前のイテレーションで隣のプロセッサが更新した領域を参照する際にはREAD\_INVALIDATEモードを使用した．
この理由は，仮に担当領域の更新にWRITE\_REMOTEモードを使用してしまうと，
第$i$イテレーションの先頭でノードの参加/脱退が発生して領域に対するプロセッサ割り当てが変化した場合に，
第$i$イテレーション以降では他のプロセッサがオーナー権を持つページに対する更新作業が常に必要になり，多量の通信が生じてしまう
（\figref{fig:jacobi}(A)）．
これに対して，WRITE\_LOCALモードを使用すれば，
第$i$イテレーションの先頭でノードの参加/脱退が発生して領域に対するプロセッサ割り当てが変化したとしても，
第$i$イテレーション終了時には，その時点でのプロセッサ割り当てに一致したページのオーナーの割り当てが実現されるため，
第$i$イテレーション以降における更新作業の対象は自分がオーナー権を持つページになる（\figref{fig:jacobi}(B)）．
このように，マルチモードread/writeをうまく利用することで，
\textbf{データへのプロセッサ割り当てが重要となるデータパラレルなアプリケーションに関して，
動的な参加/脱退に伴うプロセッサ割り当ての変化にロバストなプログラムを記述することができる}．

\begin{figure}
  \centering
  \includegraphics[scale=0.6]{jacobi.eps}
  \caption{ヤコビ反復法においてプロセッサ数を増減させた場合における，領域に対するプロセッサ割り当ての変化
    （(A)領域更新にWRITE\_REMOTEを使用した場合，(B)領域更新にWRITE\_LOCALを使用した場合）．}
  \label{fig:jacobi}
\end{figure}

\begin{figure}
  \centering
  \includegraphics[scale=0.6]{data_jacobi.eps}
  \caption{ヤコビ反復法に関する，DMIの実行時間とスケーラビリティ．}
  \label{fig:data_jacobi}
\end{figure}

\begin{figure}
  \centering
  \includegraphics[scale=0.6]{data_jacobi_dynamic.eps}
  \caption{ノードを動的に参加/脱退させる場合の，ヤコビ反復法の各イテレーションの実行時間．}
  \label{fig:data_jacobi_dynamic}
\end{figure}

まず，\figref{fig:data_jacobi}には，
さまざまなプロセッサ数に関するDMIの実行時間（DMI(time)）と速度向上度（DMI(speedup)）を示す．
\figref{fig:data_jacobi}より，32プロセッサまでスケールしており，
32プロセッサで8.90の速度向上度を達成している．
次に，ノードの動的な参加/脱退の効果を調べるため，
最初は8プロセッサで実行し，
第50イテレーション終了時に56プロセッサを追加し，
第85イテレーション終了時に48プロセッサを脱退させた場合の，
各イテレーションの実行時間を\figref{fig:data_jacobi_dynamic}に示す．
\figref{fig:data_jacobi_dynamic}より，
ノードの動的な参加/脱退に伴って動的に並列度を増減させられていることがわかる．
また，第51イテレーションと第86イテレーションの実行時間が長いのは，
更新領域に対するプロセッサ割り当ての変化に伴って，
WRITE\_LOCALモードによる更新時に，最新のページ転送を伴ったオーナー権の移動が多量に発生するためである．


現段階ではこの実験が最大のウリで，
「以上のように，単純なクライアント・サーバ方式では記述できないような，
プロセッサが密に協調しながら動作するアプリケーションに対しても計算資源の動的な参加/脱退をサポートし，
参加/脱退に相応して動的に並列度を増減できる処理系は新規性の高いものである．
この結果は，従来の処理系では計算資源の動的な参加/脱退をサポートできなかったアプリケーション領域に対しても，
DMIによるアプローチが応用できる可能性を示唆している．」というのが主張である．

\subsubsection{NAS Parallel Benchmark（EP）}
\label{sec:perform_ep}

\begin{figure}
  \centering
  \includegraphics[scale=0.6]{data_ep.eps}
  \caption{EPに関する，DMIとMPIの実行時間とスケーラビリティ．}
  \label{fig:data_ep}
\end{figure}

NAS Parallel BenchmarkにおけるEP（Class C）を題材にして，
DMIとMPIのスケーラビリティを比較するとともに，
DMIにおいてノードの動的な参加/脱退に伴って並列度を動的に変化させる効果を評価した．
なお，NAS Parallel Benchmarkは，
本家サイトに置いてあるMPIプログラムをそのまま実行させて，
システムアーキテクチャやMPIの性能評価に使う場合が多いが，
本来はシステムアーキテクチャの評価を目的としたベンチマークであり，
「どのように実装すると効率的かはシステムアーキテクチャに依存するため，
ベンチマークの仕様は``paper and pencil''としてしか規定しない（規定すべきではない）．
ただ，それだけだと実装者が困るだろうから，あくまでもサンプルとしてMPIなどのプログラムも参考までに提供しておく」
というスタンスのベンチマークである．
たとえば，ISならば，「要するにソートできればいい」という程度しか仕様として規定されておらず，
ソートのアルゴリズムなどは実装者の判断に委ねられている．
つまり，仕様を満たす限り，DMIにとって都合がいいアルゴリズムで実装したDMIプログラムと
本家サイトで配布されているMPIプログラムを比較することは，妥当な評価と言える．

EP（Class C）は，$n=2^{32}$個の乱数の組$(x_i,y_i)$を生成し，
$t_i=x_i^2+y_i^2\le1$なる$(x_i,y_i)$に関して
$\max(|x_i\sqrt{(-2\log t_i)/t_i}|,|y_i\sqrt{(-2\log t_i)/t_i}|)$の分布を求める処理である．
DMIでは，ノードの動的な参加/脱退に対応させるため，
$n=2^{32}$を128個の均等なタスクに分割し，単純なマスタ・ワーカ方式によってプログラムを記述した．
一方，MPIでは，NPB3.3-MPIのプログラムをそのまま評価に用いた．

まず，\figref{fig:data_ep}には，
さまざまなプロセッサ数に関する
DMIの実行時間（DMI(time)）と速度向上度（DMI(speedup)），
MPIの実行時間（MPI(time)）と速度向上度（MPI(speedup)）を示す．
この処理はほとんど通信を伴わないため，DMIはMPIとほぼ同等のスケーラビリティを達成している．
DMIの実行時間がMPIよりも長いのは，演算部分に関するコンパイラの最適化などが原因で，
MPIのプログラム（Fortran）では，DMIのプログラム（C言語）よりも効率的な実行バイナリが生成されたためと思われる．
次に，ノードの動的な参加/脱退の効果を調べるため，
（\I）最初から最後まで32プロセッサで実行する場合，
（\II）最初は32プロセッサで実行するが，約10秒後に96プロセッサの参加を開始させる場合，
（\III）最初は32プロセッサで実行するが，約10秒後に24プロセッサの脱退を開始させる場合
について実行時間を計測した．
なお．この実験では10秒後に参加/脱退を開始させただけであって，
実際に参加/脱退が完了するまでには数秒を要しており，
10秒を境目として一気にプロセス数が増減したわけではない．
その結果，（\I）が27.3sec，（\II）が17.5sec，（\III）が47.8secとなり，
このようなembarrassingly parallelな処理では，ノードの参加/脱退に伴って，
効果的に並列度を増減させられることがわかった．

\subsubsection{NAS Parallel Benchmark（CG）}
\label{sec:perform_cg}

\begin{figure}
  \centering
  \includegraphics[scale=0.6]{data_cg.eps}
  \caption{CGに関する，DMIとMPIの実行時間とスケーラビリティ．}
  \label{fig:data_cg}
\end{figure}

\begin{figure}
  \centering
  \includegraphics[scale=0.6]{data_cg_dynamic.eps}
  \caption{ノードを動的に参加/脱退させる場合の，CGの各イテレーションの実行時間．}
  \label{fig:data_cg_dynamic}
\end{figure}

NAS Parallel BenchmarkにおけるCG（Class B）を題材にして，
DMIとMPIのスケーラビリティを比較するとともに，
DMIにおいてノードの動的な参加/脱退に伴って並列度を動的に変化させる効果を評価した．
CG（Class B）は，$75000\times75000$のサイズの疎行列$A$に関して，
以下の手順によって$A$の最大固有値を求める：

\begin{description}
\item[手順1] $\bm x={}^t(1,1,\cdots,1)$
\item[手順2] $A\bm z=\bm x$をCG法で解く．
具体的には，$\bm z=0$，$\bm r=\bm x$，$\rho=(\bm r,\bm r)$，$\bm p=\bm r$とした上で，
以下の処理を25回繰り返す．
\begin{align*}
\bm q&=A\bm p\\
\alpha&=\rho/(\bm p,\bm q)\\
\bm z&=\bm z+\alpha\bm p\\
\rho_0&=\rho\\
\bm r&=\bm r-\alpha\bm q\\
\rho&=(\bm r,\bm r)\\
\beta&=\rho/\rho_0\\
\bm p&=\bm r+\beta\bm p
\end{align*}
\item[手順3] $\bm x=\bm z/||\bm z||$
\item[手順4] 手順2と手順3を75イテレーション繰り返す．
\end{description}

DMIでは，手順2と手順3を構成する各イテレーションの先頭でノードの参加/脱退を処理し，
その時点で参加中のノードたちで行列とベクトルを均等に横ブロック分割し，そのイテレーションを行うようなプログラムを記述した．
また，この処理で最大のボトルネックになるのは手順2のCG法内部で行われる行列ベクトル積$A\bm p$であるが，
この行列ベクトル積を，行列$A$の横ブロック分割によって最大128プロセッサで並列演算することを想定し，
行列$A$のページサイズは$75000\times75000/128\times \mathrm{sizeof(double)}$バイトとし，
各ベクトルのページサイズは$75000/128\times \mathrm{sizeof(double)}$バイトに設定した．
一方，MPIでは，NPB3.3-MPIのプログラムをそのまま評価に用いた．

まず，\figref{fig:data_cg}には，
さまざまなプロセッサ数に関する
DMIの実行時間（DMI(time)）と速度向上度（DMI(speedup)），
MPIの実行時間（MPI(time)）と速度向上度（MPI(speedup)）を示す．
\figref{fig:data_cg}を見ると，
DMIは8プロセッサまでしかスケールしておらず，
および16プロセッサ以上ではMPIよりも著しく実行時間が長い．
この原因は，プロセッサ数を$p$，行列サイズを$n$としたとき，
行列ベクトル積に関して，
MPIでは総通信量$O(\sqrt pn)$の洗練されたアルゴリズムが採用されているのに対して，
DMIでは簡単化のため，行列の横ブロック分割による総通信量$O(n^2)$のアルゴリズムを採用してしまったためである．
次に，ノードの動的な参加/脱退の効果を調べるため，
上記手順の手順2と手順3の75イテレーションのうち，
最初は8プロセッサで実行し，第26イテレーション終了時に8プロセッサを参加させ，
第51イテレーション終了時に8プロセッサを脱退させた場合の，
各イテレーションの実行時間を\figref{fig:data_cg_dynamic}に示す．
\figref{fig:data_cg_dynamic}ではノードの参加によって性能が落ちており，
当然ながら，このようなスケーラビリティの悪い処理は参加/脱退に適さない．

そして，当然ながら，MPIとDMIという2つの処理系の比較を行いたいにも関わらず，
違ったアルゴリズムの実装で比較してしまったのは，明らかな失敗である（詳しくは次節）．

\subsubsection{NAS Parallel Benchmarkの問題点（やや余談）}
\label{sec:perform_nas}

本当は，NAS Parallel Benchmarkに数種類取り組んでみたかったのだが，
不都合な点が多すぎて，かなりの時間を費やしたもののEPとCGしか評価できなかった．
また，そもそもDMIとMPIの処理系の比較を行いたいのならば，
アルゴリズムや言語は極力統一する必要があるが，
配布されているMPIプログラムがFortranで書かれていたり，
アルゴリズムが理解できなかったりしたため，結局EPもCGも統一できない状態での評価しかできなかった．

NAS Parallel Benchmarkには以下のような問題点がある：

\begin{itemize}
\item CGでは疎行列$A$が定義される必要があるが，
  NAS Parallel Benchmarkの仕様書には疎行列$A$の生成アルゴリズムが最後まで説明されておらず，
  「詳しくは配布されているFortranを読め」と書かれている．
  結局アルゴリズムはわからなかったが，
  Fortranを改造して，生成された疎行列$A$をファイルに書き出して使うことで解決した．
\item CG法を解く部分のFortranのアルゴリズム（前述の「総通信量$O(\sqrt pn)$の洗練されたアルゴリズム」）
  が理解できず，DMIに真似できていない．
\item ISに関して，仕様書に書かれている結果が間違っている．
\item MGに関して，アルゴリズムの肝心な部分が仕様書に書かれておらず（僕には）実装できない．
\item EPの要求している解精度が不適切なように思われる．
  現状のDMIのEPは仕様書の解精度を満たしていないが，見なかったことにした．
\item CGをmpich-1で32プロセッサ以上で実行すると，途中でp4\_errorが出てエラーになってしまう．
  ネットで調べると，同様の現象は他でも起きているようだが，明確な原因はわからなかった．
  OpenMPIを使うと問題が起きないため，今回の性能評価は全てOpenMPIで行った．
  なお，藤澤くん，中島くん，加辺くんに協力してもらった実験により，
  これはNAS Parallel Benchmarkの問題ではなく，
  mpich-1における非同期recv周辺の実装のバグの可能性が高いと判断している（気になる方はあとで聞いてください）．
  中島くんからもmpich-1の挙動不審が指摘されている．
  mpich-1はDebianのapt-getで入るものだが，
  mpich-1は2005以降更新されておらず，バグフィックスが行われていない可能性がある．
\end{itemize}

\subsubsection{行列行列積}
\label{sec:perform_mm}

\begin{figure}
  \centering
  \includegraphics[scale=0.6]{data_matmat.eps}
  \caption{行列行列積に関する，DMIとMPIの実行時間とスケーラビリティ．}
  \label{fig:data_matmat}
\end{figure}

\begin{figure}
  \centering
  \includegraphics[scale=0.6]{transfer.eps}
  \caption{ページ転送の木構造化（(A)read要求に対してオーナーがページを逐次転送する場合，
    (B)ページを木構造転送する場合）．}
  \label{fig:transfer}
\end{figure}

$4096\times4096$のサイズの行列を用いた行列行列積$AB=C$を題材にして，
DMIとMPIのスケーラビリティを比較するとともに，任意のページサイズを指定できることの有効性を評価した．
アルゴリズムをMPI風に記述すると以下の通りである：

\begin{enumerate}
\item プロセス0が行列$A$をプロセス数分だけ横ブロック分割し，それを全プロセスにscatterする．
\item プロセス0が行列$B$をbroadcastする．
\item 各プロセス$i$はプロセス0から送信された横ブロック部分行列$A_i$と行列$B$を用いて，
  部分行列行列積$A_iB=C_i$を計算する．
\item 各プロセス$i$は部分行列$C_i$をプロセス0にgatherする．
\end{enumerate}

DMIにおいても，read/writeベースで記述することを除けば，
MPIと同様のデータ操作が起きるアルゴリズムで記述した．

まず，\figref{fig:data_matmat}には，
さまざまなプロセッサ数に関して以下を測定した結果を示す：

\begin{itemize}
\item DMIで，行列$A,C$については各横ブロックが1ページになるようにページサイズを設定し，
  行列$B$については行列丸ごと1個が1ページとなるようページサイズを設定し，
  行列行列積を通じてページフォルトが各ページあたり1回しか発生しないようにした場合の実行時間（DMI\_normal(time)），
  その速度向上度（DMI\_normal(speedup)）
\item DMIで，行列$A,B,C$のページサイズを2KBにした場合の実行時間（DMI\_2KB(time)），
  その速度向上度（DMI\_2KB(speedup)）．
\item MPIで，scatter，broadcast，gatherの操作に集合通信を用いた場合の実行時間（MPI\_normal(time)），
  その速度向上度（MPI\_normal(speedup)）
\item MPIで，集合通信を用いずに\texttt{MPI\_Send()}による逐次転送で行った場合の実行時間（MPI\_seq(time)），
  その速度向上度（MPI\_seq(speedup)）
\end{itemize}

\figref{fig:data_matmat}より，
DMI\_2KBの実行時間およびスケーラビリティがDMI\_normalより大きく劣っており，
任意のページサイズ指定によってページフォルト回数を大幅に削減できることの有効性がわかる．
ここで，通常のOSのページサイズである4KBでなく2KBを採用した理由は，
なぜか，4KB以上だと顕著な性能低下が見られなかったためである．
2KB以下にすると，著しい性能低下が見られるようになり，
1KBにすると10分以上待っても処理が終わらなかった．
また，DMI\_2KBの実行時間のグラフは，3回の実行時間の平均値としてプロットしているが，
通信があまりにも多発するせいか，測定の度に実行時間が大きく変化するため，グラフの線が上下している．
これらの現象の詳細な解析はまだできていない．

この任意のサイズによるコンシステンシ維持は，
\textbf{粗粒度なデータアクセスを伴うデータパラレルなアプリ一般に対して有用な最適化手段}と言える．
現状のDMIの場合，オーバーヘッドの低減を度外視してしまっているため，
ページ1個を管理するための構造体のサイズが最小でも200バイトあり，
パケット1個が最小でも104バイトあるため，
コンシステンシ維持の単位を大きくすることの効果が表れやすい．

また，\figref{fig:data_matmat}より，
DMI\_normalのスケーラビリティはMPI\_normalよりも大きく劣るが，
DMI\_normalとMPI\_normalとMPI\_seqの結果を比較すると，
その原因の大部分がMPIの集合通信に起因しているとわかる．
特に影響が大きいのは行列$B$のbroadcastであり，
現状のDMIでは，\figref{fig:transfer}(A)のように，
ページをキャッシュするノード（DOWN\_VALIDまたはUP\_VALIDなノード）を常にオーナーの直下に配置する構造になっているため，
read要求を発行してきたノードたちへの最新ページの転送がオーナーによって逐次化され性能低下につながっている．
これに対する解決策としては，\figref{fig:transfer}(B)に示すように，
オーナーにread要求が到着した際には，
オーナーが，すでにページ転送を完了したノードに対して実際のページ転送処理を動的に委譲することによって，
ページ転送を全体として木構造化させるなどの工夫が考えられる．

\section{今後の方向性}

\subsection{「実用的な」アプリをクラスタ間でマイグレーション}

現状のDMIは，全対全のコネクションを張ったり，
参加/脱退時にグローバルロックを取得するなど，
各ノードが「大局的な」知識に基づいて動作するため，
まだ大規模な環境で動作する設計にはなっていない．
これを改善し，\textbf{「局所的な」知識に基づいて動作するプロトコルを作り上げるのがDMIの最終目標}であるが，
現状のままでも，効率は悪いかもしれないが，計算を継続したまま，
参加/脱退を通じてクラスタからクラスタに処理をマイグレーションすることは原理的に可能である．
もちろん，処理系を評価する上ではNAS Parallel BenchmarkのEPで評価しても良いのだが，やはりインパクトに欠ける．
そこで，\textbf{従来のクライアント・サーバベースの処理系では，
クライアントは自由に参加/脱退できてもサーバは自由に参加/脱退できなかった「実用的な」アプリケーションに対して，
DMIではそれもできる}ということを示したい．

具体例としては，ユーザからの重いリクエストを受け付けるサーバノード数個と，
そのリクエストを処理する計算ノード多数個から構成される，クラスタA上のWebサーバシステムが考えられる．
クラスタA内の計算ノードを動的に参加/脱退させるとWebサーバシステム全体のスループットが増減するのが観測でき，
さらにクラスタAで計画停電が起きる際には，
Webサーバシステムの運用を継続したまま，
サーバノードも含めてクラスタBに移動できたらおもしろいと思う．
（当然，サーバノードのIPアドレスが変わった場合に，
ユーザがどうやって新しいサーバノードに接続するかなどの現実的な問題はあるが，
Webサーバシステムとしての運用が継続するという部分が実現できればそれで良いとする．）

何か，他におもしろそうなアイディア（画像処理？，自然言語？，・・・etc）があれば教えていただけるとうれしいです．
以下の条件を満たすことが理想です：

\begin{itemize}
\item （動的な並列度変化が見れないとおもしろくないので，）本質的にembarrassingly parallelな処理であること
\item （ファイルに頼っては意味がないので，）メモリ上の処理で完結する処理であること
\item （DMIのプログラムは，既存プログラムを少し改造することでは得られず，
まずpthreadで記述して動作を確認し，
それを\texttt{DMI\_read(...)}/\texttt{DMI\_write(...)}に
翻訳するという非常に面倒な作業を行う必要があることを踏まえ，）DMIで記述できるレベルに簡単な処理であること
\item 少しは実用的と思える処理であること
\end{itemize}

\subsection{粗粒度なデータアクセス中心の処理に対する最適化手法の評価}

DMIは，従来の多くの分散共有メモリとは少し性格が違う部分がある．

僕が知る限り，従来の多くの分散共有メモリにおける最適化手法では，
データアクセスが細粒度でアクセスが頻繁に干渉するような処理に対する研究が中心である．
多様な緩和型コンシステンシモデルやMultiple Write型のプロトコルなどは，
細粒度なアクセスが競合する際に並列性を確保するための工夫と捉えられる．
また，分散共有メモリならではのプログラム記述の容易さも重要視され，
page-basedな分散共有メモリであれば，
OSのメモリ保護機構を利用することで，通常の変数代入文で仮想共有メモリにアクセス可能とするのが主流である．

これに対してDMIは，
そもそもの目的は参加/脱退のサポートであり，
\textbf{分散共有メモリを利用する理由は，参加/脱退を容易にサポートするためという部分にしかない}．
また，参加/脱退に相応して動的に並列度を増減させることが目的なので，
データアクセスが粗粒度なスケーラブルな処理が対象である．
それゆえ，プログラム記述の容易さも重視しておらず，
\texttt{DMI\_read(...)}/\texttt{DMI\_write(...)}によるプログラム記述は，
まさにMPI関数的なノリであって，
プログラマに対して明示的なチューニング手段を提供して性能を引き出すことを目指している．
要するに，（かなり大げさな言い方だが，）
DMIは，従来の分散共有メモリがあまり相手にしてこなかったようなスケーラブルな処理の性能向上を意図した分散共有メモリと言え，
その意味で，DMIをベースとして
\textbf{データアクセスが粗粒度な処理に対する分散共有メモリの最適化手法というシナリオ}を考えることには多少の新規性があるように思う．
具体的には，任意粒度でのコンシステンシ維持，非同期read/write，
マルチモードread/write，ページ転送の木構造化の4つを提案している．
このうち，任意粒度でのコンシステンシ維持はすでにCRLやHIVEなどで提案されており，
region-basedな手法として定着しているので新規性はない．
しかし，非同期read/writeとマルチモードread/writeは，
\texttt{DMI\_read(...)}/\texttt{DMI\_write(...)}という関数呼び出し型のプログラム記述を
採用しているからこそ実現できる機能である（非同期read/writeに似たものはあるが）．
また，ページ転送の木構造化に関しても，調べた限りでは例を見ない．

以上を踏まえて，データアクセスが粗粒度な処理に対する分散共有メモリの最適化手法というシナリオで，
もう少し評価を進めてみたいと思う．
上記の4手法のうち，まだ未実装なのはページ転送の木構造化なので，
とりあえず木構造が$m$分木になるように実装してみて，$m$による効果を調べる予定である．
現在のDMIは，$m=\infty$としたものと捉えられる．
なお，現状のDMIでは，オーナーからのメッセージを受信側で順序制御しており，
オーナー発のメッセージの転送経路は問題にならないため，
ページ転送の木構造化は現在のプロトコルに単純に組み込める（予定である）．


\end{document}