\documentclass{ipsjpapers}
\usepackage{graphicx}
\usepackage{graphics}
\usepackage{fancybox}
\usepackage{eclbkbox}
%\copyrightnotice{情報処理学会プログラミング研究会 発表資料  2005年8月3日}

% 巻数，号数などの設定
\setcounter{巻数}{46}
\setcounter{号数}{4}
\setcounter{volpageoffset}{1}
\受付{16}{11}{28}
\採録{17}{2}{4}

% ユーザが定義したマクロなど．
\newcommand\slant{/\penalty\exhyphenpenalty}
\catcode`\/=\active
\let/=\slant

%\checklines	% 行送りを確認する時に使用
\begin{document}
% 和文表題
\title[マイグレーションを支援する分散集合オブジェクト]
{マイグレーションを支援する分散集合オブジェクト}

% 英文表題
\etitle{Distributed Aggregate with Migration}

% 所属ラベルの定義
\affilabel{TUniv}{東京大学\\
University of Tokyo}

% 和文著者名
\author{高橋 慧\affiref{TUniv}\and
	  田浦 健次朗\affiref{TUniv}\and
	  近山 隆\affiref{TUniv}}

% 英文著者名
\eauthor{Kei Takahashi\affiref{TUniv}\and
	  Kenjiro Taura\affiref{TUniv}\and
	  Takashi Chikayama\affiref{TUniv}}

% 連絡先（投稿時に必要．製版用では無視される．）
\contact{
高橋 慧
〒113-8656 東京都文京区本郷7-3-1
東京大学大学院 情報理工学系研究科 電子情報学専攻 田浦研究室
TEL: (03)5841-6398\qquad FAX: (03)5841-6398
email: kay@logos.ic.i.u-tokyo.ac.jp
}

% 和文概要
\begin{abstract}

グリッド環境におけるプログラムは，与えられた資源を最大限活用するために
動的なプロセッサ数の増減に対応することが求められている．一方でプログラ
ムの記述においては，プロセッサ数の増減を意識しないような書き方が出来る
ことが望ましい．

既存の分散オブジェクトモデルでは，オブジェクト指向により簡単な記述が行
え，オブジェクトのマイグレーションによりプロセッサの増減にも対応できる．
しかし，分散配列などプロセッサ間にまたがる大きなデータを記述しようとす
ると，データとオブジェクトの対応が動的に変化してしまい，本来のプログラ
ムの記述が非常に複雑になってしまう．

% 現状では多くの並列プログラムはメッセージパッシングを用いて記述されてい
% るが，これは多くの場合通信相手の指定にプロセッサ番号を用いるため，プロ
% セッサ数増減に対応するにはデータとプロセッサ番号の対応をプログラマが
% 管理する必要があり，記述は難しい．

本発表では，大きな配列などインデックスにより識別される集合を用いる際，
プロセッサ数の変化に対応した並列プログラムを簡単に記述できる，「分散集
合オブジェクトモデル」を提案する．これにより，プロセッサ間に断片として
分散しているデータが，プログラマからは一つのオブジェクトとして見えるよ
うになる．メソッドの呼び出しはインデックスの範囲を指定して行うため，プ
ログラムはデータの配分を意識せずに記述できる．実装においては要素と断片
の対応を分散保持し，メッセージの集中を防いで性能を損なわないようにした．

我々はこの分散集合オブジェクトの処理系を実装し，その上でアプリケーショ
ンを記述して動作の確認と性能評価を行った．

\end{abstract}

\begin{eabstract}

In Grid environment, it is required to allow to change the number of
processors that participates in the computation in order to utilize
available resources efficiently.  At the same time, object-oriented
programming model is desirable for easy description. With distributed
object models, a program can allow to change the number of processors
by object migration. However, with this model, it is very hard to
implement distributed large data structures -- such as distributed
array -- allowing to change the number of processors.

We propose "distributed aggregate model" as an extension of
distributed object model. It handles a data structure identified with
indices, like distributed array. In our distributed aggregate model,
each object can be distributed among processors as fractions, but
looks like one object to programmers. Thus a programmer can write
programs without worrying about its distribution.  Every processor has
the conversion table of indices and processors, so messages do not
concentrate on one processor.

We implemented this framework, wrote a programming example of partial
differential equation and n-body problem. The program operated
correctly when the number of processors changes dynamically, and we
evaluated its performance.
\end{eabstract}

% 表題などの出力

\maketitle

\section{はじめに}

グリッド環境においては，利用可能な資源は負荷の増減や故障により変動する．
このため，与えられた資源を最大限活用するためにはプログラムはプロセッサ
の増減に対応する必要がある．プロセッサの増減に対応するためには，動的に
データ・タスクを移動させ，他のプロセッサにデータが移動したことを伝達す
る必要がある．

現状では多くの並列プログラムはメッセージパッシングを用いて記述されてい
るが，これは多くの場合通信相手の指定にプロセッサ番号を用いるため，プロ
セッサ数が増減すると動的にメッセージの送信先を変える必要がある．送信先
を指定するためにはプログラマがデータとプロセッサの対応を把握するコード
を書く必要があり，記述は難しい．

分散オブジェクトではオブジェクト指向の記述が行え，またデータの識別にプ
ロセッサではなくオブジェクトを用いるので，あるオブジェクトがあるプロセッ
サから他のプロセッサに移動しても，メソッド呼び出し先を変更する必要はな
い．しかし，分散配列などプロセッサ間にまたがる大きなデータを扱う場合に
は，オブジェクトを分割したり併合したりする必要が生じるので，メソッド呼
び出しの対象となるオブジェクトを変更する必要が生じ，記述は簡単ではない．

本発表では，大きな配列などインデックスにより識別される集合を用いる際，
プロセッサ数の変化に対応した並列プログラムを簡単に記述できる，「分散集
合オブジェクトモブル」を提案する．これにより，プロセッサ間に断片として
分散しているデータが，プログラマからは一つのオブジェクトとして見えるよ
うになる．メソッドの呼び出しはプロセッサ番号ではなく，オブジェクトの識
別子とインデックスの範囲を指定して行う．このため，プログラマはプロセッ
サ間でのデータの移動を意識する必要がない．実装においては要素と断片の対
応を分散保持し，メッセージの集中を防いで性能を損なわないようにした．

我々はこの分散集合オブジェクトの処理系を実装し，その下で偏微分方程式・
N体問題のアプリケーションを記述して動作の確認と性能評価を行った．


\section{既存の並列プログラミングモデル}

ここでは並列プログラム記述のための手法として，メッセージパッシング，分
散オブジェクト，Concurrent Aggregateを用いた際の特徴と問題点について述
べる．

\subsection{メッセージパッシング}

メッセージパッシングモデルは，最も基本的で，広く使われている並列計算モ
デルである．MPI\cite{mpi}が一例として挙げられる．このモデルではsend()
とrecv()の二つの関数が用意され，相手プロセッサを指定して通信を行う．

一般的なメッセージパッシングモデルは，プロセッサの増減に対応するのが難
しい．一般にメッセージはプロセッサ番号を指定して送られるが，プロセッサ
数が変化した場合，動的にメッセージを送信する先のプロセッサを変える必要
があり，記述は簡単ではない．

一方で，このモデルは下層で実際に行われる処理に近く，呼び出し
自体のコストが小さいため，無駄の無いプログラムを記述することができる．
また，ローカルのデータとリモートのデータがはっきりと区別され，ローカル
のデータには逐次と同じ速度でアクセスできる．

Phoenixモデル\cite{phoenix}は，メッセージパッシングモデルを拡張したも
のである．このモデルでは，計算前に物理的なプロセッサIDとは別の，複数の
仮想的なプロセッサ番号(仮想ノード番号)の集合を考える．そして，この仮想
ノード集合を計算に参加しているプロセッサで過不足無く分割する．計算に参
加する場合は，他のプロセッサから集合の一部を割り当てられ，離れる場合は
他のプロセッサに集合を委譲する．ここで，メッセージの送信はこの番号を指
定して行い，送信されたメッセージは指定されたを持つ番号をプロセッサによっ
て受信される．プロセッサが担当する番号は変化し得るが，メッセージの送信
先を変更する必要は無いため，プロセッサ数の増減に対応したプログラムを容
易に記述できる．


% ．一方で記述に関しては，通常のメッセージパッシン
% グから改善されていない．

% メッセージの送信先のプロセッサの指定方法として，仮想的な
% 整数の集合を用いることにより，プロセッサが増減してもAPIレ
% ベルではメッセージの送信先を変更する必要がなくなっている．
% 計算前にある整数集合を考え，これを計算を担当するプロセッサで過不足無く
% 分割する．

% \subsubsection{RMAを追加したモデル}
% MPI2\cite{mpi}では，メッセージパッシングに加えてリモートメモリアクセス
% (RMA)の機能を備えることで，記述効率を向上させている．
% MPI2での実装では，予め一定の仮想のメモリ番地を宣言し，この領域をリモート
% のメモリに対応付ける．そして，mpi\_put() / mpi\_get()関数を通じてこの番
% 地にアクセスすると，予めリモートのプロセッサに待機していたRMA用のスレッ
% ドと通信が行われ，アクセスが可能になる．

% 基本はメッセージパッシングであり，記述はメッセージパッシングを併用して記
% 述できるため，純粋な分散共有メモリに比べて性能の向上が図りやすい．
% 一方で，メッセージの送受信にはプロセッサ番号を指定するため，プロセッサプ
% ロセッサの増減への対応は困難なままである．RMAについても，前もって宣言し
% た番地にしか使えないので，動的にデータとプロセッサの対応が変わることは考
% 慮されていない．

\subsection{共有メモリモデル}

共有メモリとは，複数のプロセッサが特定の領域のメモリを共用し，ローカル
のメモリと同様に書き込みや読み出しが出来るシステムである．
アクセスされるデータは場合によってはリモートにあるため，下層で通信が行
われる．

このモデルは，プロセッサ増減への対応が容易である．メモリ番地と実際にそ
のデータを持つプロセッサの対応付けを動的に変えられるようにすると，プロ
グラムの記述を変えずにプロセッサの増減に対応できるようなシステムを構築
できる．
% ただし，データの配分の変更と共に仕事の配分を変更するための記述が必要である．

一方で，どの番地がどのプロセッサに割り当てられているかを意識せずにプロ
グラムを書くと，離れたプロセッサにあるメモリへのアクセスが多く回数発生
する．望ましいのは，離れたメモリに対しての処理はそのデータを持つプロセッ
サが行うことである．このためにはプロセッサとメモリ領域の対応をプログラ
マが把握する必要があり，本来の記述の容易さは損なわれてしまう．

% プロセッサ間の通信が高速な並列計算機であればこれは問題にならない
% が，グリッド環境においては通信路は非常に低速であり，ブロックする時間が
% 長くなり，速度が低下してしまう．ページキャッシュを用いた場合でも，ラン
% ダムなアクセスでは事情は同じである．

\subsection{分散オブジェクトモデル}
分散オブジェクトはオブジェクト指向を基本に，リモートのオブジェクトについて，
メソッド呼び出し(RMI : remote method invocation)が行えるものである．
呼び出されたオブジェクトを持つプロセッサではメソッドの処理を行い，必要
に応じてその結果を呼び出し元のプロセッサに返す．
RMIに加え，一度生成されたオブジェクト自体を他のプロセッサに移動させる，
マイグレーションと呼ばれる技術を組み合わせると，プロセッサ数の増減に対応
することができる．マイグレーションにより，そのオブジェクトに関してのメソッ
ドの処理もそのプロセッサに委譲されるから，仕事の分担についての記述は変更
しなくてもよい．

記述はオブジェクト指向により簡単に行え，自然な形でデータとタスクの関連
性が保たれるためという点がある．外部のプロセスは，オブジェクトのメソッ
ドを通じてしかデータにアクセスしないので，分散共有メモリのようにプロセッ
サが不必要にリモートのメモリにアクセスすることがない．
しかし，単純にRMIとマイグレーションを提供するだけでは，分散配列のよう
なプロセッサ間にまたがったオブジェクトは簡単に記述できない．これを以下
に示す．

大きなデータ集合は，各プロセッサが断片オブジェクトを持つことにより実現
される．ここでオブジェクトは複数のプロセッサにまたがって置くことは出来
ないため，プロセッサの増加に対応するためには動的に既存のオブジェクトを
分割するか，予め各プロセッサがたくさんの小さなオブジェクトを持っている
必要がある．前者はプロセッサ増加の前後であるデータを保持するオブジェ
クトが変わってしまうので，プログラムの記述が難しくなる．後者はプログラ
ムの記述は楽だが，データの分割単位が小さいと実行効率が悪くなってしまう
し，分割単位が大きいと任意のプロセッサの増加に対し対応できない．

つまり，プロセッサの増減には基本的には対応出来るが，プロセッサ間にまた
がる大きなデータを扱う際には問題がある．


\subsection{Concurrent Aggregates}
Concurrent Aggregates\cite{ca}とは，複数のプロセッサに断片として存在し
ているオブジェクトに対して，それらを全体で一つのオブジェクトと見てメソッ
ドを呼び出せるようにしたものである．このモデルでは，断片オブジェクトの
宣言において，"この操作を他の全ての断片についても行う"という記述が出来
るようになっている．外部からある断片のメソッドを呼び出すと，そのメソッ
ド呼び出しが条件によっては他の断片に中継され，最終的にデータ全体にアク
セスができる．

このシステムでは，断片オブジェクトが分割・併合・マイグレーションしても，
そのオブジェクトを用いる人にとっては，あたかも一つの大きなオブジェクト
であるように扱うことができる．メソッドの処理はオブジェクトを持つプロセッ
サが行うので，タスクの配分は自然に行われる．

一方でこのシステムでは，インデックスによって識別される集合でも，特定の要
素に直接アクセスできない．可能なのは，任意の一断片オブジェクトにアクセス
することで，これにより全ての断片オブジェクトへ要素の問い合わせのメッセー
ジが呼ばれる．しかし，配列のようなデータに対し毎回このような操作を行うの
は，呼び出しコストが大きすぎる．


% ok
\section{提案モデル}
本発表では，プロセッサ数が変化する環境において簡単に記述が行え，かつ性
能を損なわない「分散集合オブジェクト」を用いた記述モデルを提案する．
分散オブジェクトを基本にしているが，オブジェクトはプロセッサ間にまたがっ
て存在でき，また断片のマイグレーションによりプロセッサの増減に対応でき
る．


\subsection{対象とする集合}
本システムは，配列やハッシュ表のようにインデックスにより識別される集合
を対象とする．並列プログラムにおいては，このデータは断片に分割され，各
プロセッサに配置されている．
これらは逐次プログラムにおいてはインデックスからデータの
アドレスを簡単に計算できるため，高速にアクセス可能である．またプロセッ
サ数が定まっている並列プログラムにおいても，あるデータを持つプロセッサ
を簡単に計算できる．一方でプロセッサ数が変化する
環境においては，プロセッサとデータの対応は動的に変化するため，データに
アクセスするプロセッサはこの対応を保持する必要がある．


\subsection{記述モデル}
プログラマは，まずクラス定義を記述する．ここで定義するクラスはデータ全
体の一部を持つ断片を表し，メソッドもそれに応じて書かれる．その後，プロ
グラマはインスタンスを作成する．外部からはこのオブジェクトは全体で一つ
に見えるため，プログラマはデータの配分を意識せずにメソッドを呼び出すこ
とができる．またプロセッサの増減に対しては，外部からメソッドを呼ぶこと
で，断片を退避させたり受け入れたりすることができる．

なおメソッドの同期的な呼び出しは色々検討すべき点があるので，今回の実装
では非同期的呼び出しのみをサポートし，メソッドは返り値を持たない．本章
ではこれらの詳細について述べる．


\subsubsection{断片クラス定義とメソッド呼び出し}
本システムで対象とするデータ集合はインデックスを持ち，断片はあるインデッ
クス集合に対応したデータを持っている．例えば，ある断片が[20-30)という
インデックス集合を持っていれば，その断片はインデックス[20-30)に対応し
たデータを持つようになっている．ここで，メソッドはインデックス範囲を指
定して呼び出される．すると，指定されたインデックス範囲と重なりを持つよ
うな全ての断片に対して，その重なりのインデックス集合を引数にメソッドが呼び出される．
例えば，[0-10)・[10-20)・[20-30)という断片が存在するとき，[5-15)という
範囲を指定してメソッド$method\_a()$を呼び出すと，[0-10)を持つ断片では
[5-10)を引数に，[10-20)を持つ断片では[10-15)を引数に$method\_a()$が呼び
出される．この様子を図\ref{fig:rmi}に示す．

\begin{figure}[tb]
\includegraphics[width=7cm,keepaspectratio,clip]{rmi.eps}
\caption{メソッド呼び出し}
\label{fig:rmi}
\end{figure}

ここで，メソッドの呼び出しは一続きの処理として行われ，処理途中にオブジェ
クトが分割されることはない．また，あるメソッドの実行中に他のメソッドが
開始されることもない．
メソッドの記述において，自分の断片内に存在しないデータにアクセスす
る必要が生じたときには，メソッド内から再度別のメソッドを呼び出すことに
よりデータにアクセスする．これにより，プログラマは断片内のデータと外部
のデータを明確に区別してプログラムを記述できる．

実例として，分散配列の指定した要素をインクリメントする擬似コードを以下
に示す．この記述によって，配分によらず要素[15-25)をインクリメントでき
る．

\begin{breakbox}
\begin{verbatim}
void DArray::increment(IndexSet *is){
  foreach (index <- is)
　  data[index]++;
}

int main(){
  ...
  /* DArrayのインスタンスをArrayとする */
  Array->increment ([15-20));
  ...
}
\end{verbatim}
\end{breakbox}


\subsubsection{マイグレーション}
プロセッサの増減への対応は，マイグレーションにより行う．プログラマは，
予めメソッド定義においてその断片オブジェクトを分割する$split()$・併合
する$merge()$，バイト列に変換する$serialize()$とバイト列からのコンスト
ラクタ($deserialize()$)のメソッドを記述する．これらのメソッドはシステ
ムにより自動的に呼び出される．

本処理系を用いるときには，$join()$・$leave()$のメソッドを持つ
$da::Manager$オブジェクトが提供される．
処理の実行中にプロセッサが新しく加わった場合は，このプロセッサが
$join()$を呼び出すことにより，既に計算に参加しているプロセッサのうち一
つに要求が送信される．このとき，プロセッサの選択は全インデックス範囲か
らランダムに一つのインデックスを選ぶことにより行われる．$join()$要求を
受けたプロセッサは自分の持つ断片を二つに分割し，要求元のプロセッサに返信する．

実行中にプロセッサが脱退する場合は，そのプロセッサが$leave()$を呼ぶこ
とにより，自分の持つ断片オブジェクトが自分以外のランダムなインデックス
に送信される．要求を受け取ったプロセッサは，
送信された断片を既にある断片と併合したり，それが出来ない時には断片のま
まで登録する．

システムによって呼び出される$split()$・$merge()$・$serialize()$はメソッ
ド実行の合間に行われるため，オブジェクトがメソッドの実行中に分割される
ことはない．


\subsubsection{返り値とマイグレーション}
今回の実装では，システムは同期的なメソッド呼び出しをサポートせず，プロ
グラマはメソッドを非同期的なメソッドに分割して記述する必要がある．この
ためRMIのためのメソッドは返り値を持たない．この理由を以下に述べる．

同期的なメソッド呼び出しをサポートするシステムでは，スレッドがメソッド
呼び出しの処理を待ってブロックしている状況が頻繁に発生する．ここで，ブ
ロックしているスレッドを持つオブジェクトを分割・併合できるようにした場
合，メソッドの実行中にその断片オブジェクトが持つデータ集合が変化するこ
とになり，円滑な記述は行えない．ブロックしているスレッドを持つオブジェ
クトは分割・併合できないことにすると，マイグレーションできる機会は事実
上無くなってしまう．% また返り値についても，分割によって

そこで本システムでは，同期的なメソッドの呼び出し側の処理を「呼び出し前
の処理」と「呼び出し後の処理」の二つに分割して記述させる．
メソッド呼び出しは，呼び出し元のインデックス範囲を引数に行われ，返り値
を返すメソッドは，このインデックス範囲に対し返り値に相当する値を指定し
て「呼び出し後」のメソッドを呼び出す．この様子を図\ref{fig:mm}に示す．

これにより，メソッド呼び出しの各切れ目でオブジェクトのマイグレーション
が可能になる．またメソッドを呼び出したオブジェクトが返り値を待っている
ときに分割されても，双方に返り値のデータが送信されるようなプログラムを
記述することができる．


\begin{figure}[tb]
\includegraphics[width=2in,keepaspectratio,clip]{mm.eps}
\caption{返り値を挟んでのメソッドの分割}
\label{fig:mm}
\end{figure}


\section{処理系の実装}
先に述べたようなメソッド呼び出し・マイグレーションを実現する処理系を，
C++でPhoenixライブラリを用いて実装した．実装にあたっては，スケーラビリ
ティを損なわないよう，一プロセッサに処理が集中しないようにした．

\subsection{ルーティング}
プロセッサ数が変化する環境においては，要素とプロセッサの対応表を動的に
更新する必要がある．一プロセッサがこの表を集中管理すると実装は容易だが，
このプロセッサにメッセージが集中し，性能上ボトルネックとなる．
このため，本システムではルーティング表を各プロセッサが分散保持し，
メッセージは各断片に直接届けられるようになっている．
本処理系では，Phoenixライブラリ\cite{phoenix}がこの処理を行ってくれる．
% この実装にはPhoenixライブラリ\cite{phoenix}を利用している．

Phoenixライブラリでは，計算前にある整数集合を考え，これを計算を担当す
るプロセッサで過不足無く分割し，メッセージはこの番号を指定して送信され
る．本ライブラリではインデックス一つにPhoenixの整数番号一つを対応付け，
メソッド呼び出しのメッセージは，指定されたインデックス集合のうち一つの
インデックスを取って送られる．Phoenixでは番号とプロセッサの対応表を分散
保持しているので，本ライブラリでもこれを利用することで，メソッド呼び出
しのメッセージを直接目的とするプロセッサに送信できる．


\subsection{メッセージの配送}
メソッド呼び出しはインデックス集合を指定して行われ，各断片で保持するイ
ンデックスと重なりを取ってメソッドが呼び出される．メッセージはまず範囲
の先頭のインデックスに送られる．受け取ったプロセッサでは，
この引数を，自分が保持するインデックス集合との重なりとそれ以外の部分に
分割する．そして，重なりを引数にメソッドを呼び出し，残りのインデックス
集合を同様に転送する．

我々は同時にツリー状にメッセージが中継されるアルゴリズムも実装した．
これは，指定されたインデックス集合がある閾値以上であればこれを分割し，
それぞれの先頭のアドレスに送信するものである．インデックス集合が閾値よ
り小さくなったら，メッセージは分割せずに送信する．
閾値の選択が適切であれば，この方法は広範囲に対する呼び出しが短時間で行
えるが，一回の呼び出しに対し一つの断片が複数回のメソッド呼び出しを受け
る可能性がある．


% \subsection{マイグレーション}
% あるプロセッサがマイグレーションに関するメッセージを受け取ると，そのプ
% ロセッサはオブジェクトの分割によるマイグレーションは，メソッド実行の合間に
% 現在のところ一プロセッサ単位での


\section{アプリケーションの記述例}
本システムを用いて，SOR法とN体問題の記述を行った．SOR法は二次元の配列を
用い，隣接する断片間でデータを交換し，全要素について残差の集計を行う．
N体問題では一次元の配列を用い，全ての二つの要素のペアについて位置から
互いの間に働く力を計算する．

\subsection{SOR法}
\subsubsection{問題の概要}
SOR法は偏微分方程式を反復法によって解くものである．
二次元の配列を，上下左右の値を用いて更新する．端の要素は境界条件に基づ
いて更新する．全要素の更新が終わったら，残差(更新された値と元の値の差)
を計算して全範囲について集計する．集計した値が閾値未満であれば終了し，
そうでなければ再度更新を行う．

このプログラムを並列環境で実行するには，配列要素を各プロセッサに分け与
えて，各プロセッサが保持する要素を更新する．プロセッサ間の境界に位置す
る要素では，更新の際に他のプロセッサのデータが必要になるので適宜要求し
て更新する．更新が終わったら，残差を1プロセッサに集めて集計し，閾値と
比較してループを続けるか終了するかを判断する．この擬似コードを以下に示
す．

\begin{breakbox}
\begin{verbatim}
while(残差 > 閾値) {
  境界のデータを交換
  保持する配列要素を更新
  残差を1プロセッサで集計
}
\end{verbatim}
\end{breakbox}



\subsubsection{記述方法}
以下に，このシステムを用いて記述した擬似コードを示す．
プログラムは分散集合オブジェクト$SORMatrix$のインスタンスを作り，全インデッ
クス範囲について$calc()$を呼ぶことにより開始される．$SORMatrix$は必ず矩形領
域を持つものとし，一プロセッサに矩形でない領域を配置する場合は二つ以上
の断片に分けるものとする．

$SORMatrix$の基本になる関数は$calc()$と$sumup()$である．$calc()$は，その回のルー
プで初めて呼ばれた場合，その断片の端のデータを隣接するプロセッサに送信
し，断片が持つ配列の値のうち更新できる部分を更新する．その後，引数のデー
タを用いて境界を更新し，全範囲の更新が終わったら残差をプロセッサ0に送
信する．

$sumup()$は引数にインデックス範囲と残差を取り，それまでにその断片に対し
送信されてきたインデックス範囲と残差を集計する．受け取るべき残差が全て
到着したら閾値との比較を行い，閾値より大きい場合はループを続ける．この
場合は，全インデックス範囲に対し$calc()$を呼ぶ．閾値より小さければ，結果
を出力させて終了する．


\begin{breakbox}
\begin{verbatim}
class SORMatrix : public da::Fraction {
  void calc(da::IndexSet *is, da::msg *m){
    if(現在のステップ最初の呼び出し){
      calc(隣接するインデックス集合, 自分の境界のデータ)
      内部を更新
    }
    引数のデータを用いて周囲を更新
    if(未更新の領域が存在) return;
    残差を集計・次のステップへ
  }
};
\end{verbatim}
\end{breakbox}


\subsubsection{性能}
このプログラムを100台を用いた環境でプロセッサの増減のもと正しく動作し
た．また性能評価のため，行列サイズを一辺20000に設定して4台から100台で
実行した．測定環境はCPUがXeon2.4GHz・メモリ2GByteのマシンが1Gbpsで接続
されたクラスターである．また，データの分割は予め二次元的に均等に割り付
けを行った．
一回ごとに残差の集計のため全プロセッサが同期されるので，一台のプロセッ
サについて一回のループにかかった時間からGFlops値を計算した．これを図
\ref{fig:cg-mflops}に示す．また，この際内部の更新にかかった計算時間
(cputime)とループ全体の時間の内訳も測定した．これを図\ref{fig:cg-time}
に示す．


\begin{figure}[h]
\includegraphics[width=7cm,keepaspectratio,clip]{cg-mflops.eps}
\caption{SOR法のGFlops値}
\label{fig:cg-mflops}
\end{figure}

\begin{figure}[h]
\includegraphics[width=7cm,keepaspectratio,clip]{cg-time.eps}
\caption{SOR法の時間内訳}
\label{fig:cg-time}
\end{figure}

GFlops値は100台までスケーラブルな性能を示した．一台当たりに換算すると，
4台では576MFlops，100台では413MFlopsとなっている．比較のために，同じ計
算処理を用いた逐次版では590MFlopsであったので，通信によるオーバーヘッ
ドは3割程度に抑えられている．

また，実行中にプロセッサを増加させたときの結果を図\ref{fig:join}に示す．
初め16台で均等にデータを割り付けて実行していた計算に，44台のプロセッサ
を追加した．
この時の一ループごとのGFlops値の変化の様子を図\ref{fig:join}に示す．

\begin{figure}[h]
\includegraphics[width=7cm,keepaspectratio,clip]{join.eps}
\caption{join時のGFlops値変化}
\label{fig:join}
\end{figure}

参加前は8.6GFlopsだったのが，図で示した部分で44台のプロセッサが参加し
たことで，マイグレーションにより一時的に処理が遅くなっている．その後は
ルーティングの変更により値は変動しているが，参加後は約31GFlopsで安定し，
プロセッサ参加によって3.6倍の高速化が図られた．
今回の実装では，新しく参加したプロセッサはランダムなインデックスに対し
参加要求メッセージを送信し，受信した断片は均等に二分割されて，片方を返
す．また，このアプリケーションは全体の性能が最も遅いプロセッサに律速さ
れてしまうため，少ない台数を参加させても性能の向上は見られなかった．

また，あるプロセッサが参加要求を出してから参加が完了するまでの時間は
7.5秒で，うちオブジェクトの分割に2.2秒・復元に2.1秒がかかっている．


\subsection{N体問題}
\subsubsection{問題の概要}
N体問題は，N個の物体の間に働く力をシミュレートするものである．
全ての物体の組み合わせについて力を計算して，全ての物体について力を計算
出来たら速度・位置を更新する．このアルゴリズムは以下のようになる．

\begin{breakbox}
\begin{verbatim}
A[size] : 物体リスト
指定した時間ループ{
  全ての(i,j)について
    A[i]とA[j]の間の力を計算
  時間を進める
}
\end{verbatim}
\end{breakbox}

\subsubsection{記述方法}

このプログラムを本処理系を用いて記述した結果を以下に示す．なお，これは
最も簡単なものを示しており，実際に性能測定をしたものは少し異なる．
処理はcalc()を全領域について呼び出すことにより開始される．calc()は引数
に物体の位置・質量のリストを取る．まずcalc()がそのステップで初めて呼び出
されたときには，その断片が持つ物体のデータを引数に，全てのインデックス
集合に対してcalcを呼び出す．その後，引数にデータがあれば，そのデータを
もとに各物体にかかる力を計算する．その断片が全ての物体のデータを受け取
って力を計算したら，時間を進めて位置・速度を更新する．

\begin{breakbox}
\begin{verbatim}
class NBody : public da::Fraction {
  whole_is : 全体のインデックス集合
  own_is   : 保持するインデックス集合
  void calc(da::IndexSet *is, 物体データ){
    if(現在のステップ初の呼び出し){
      calc(whole_is, 保持する物体のデータ)
    }
    引数の物体データを用いて力を計算
    if(更新完了){
      時間を進める
      calc(own_is)
    }
  }
};
\end{verbatim}
\end{breakbox}


\subsubsection{性能評価}
このプログラムを物体数5000に設定し，プロセッサ数を1-49台の環境で実行し
，一回のループにかかった時間からGFlops値を計算した．


\begin{figure}[h]
\includegraphics[width=7cm,keepaspectratio,clip]{nbody.eps}
\caption{N体問題のGFlops値}
\label{fig:nbody}
\end{figure}

GFlops値は49台で頭打ちとなってしまった．一台当たりに換算すると，
4台では134MFlops，49台では73MFlopsとなっている．これは用いたアルゴリズ
ムにおいて，プロセッサ間の仕事量にばらつきがあるためだと考えている．


\section{おわりに}
本発表では，分散配列のようなプロセッサ間に分散する集合を扱うプログラム
において，オブジェクト指向で記述が行えてかつプロセッサ数の増減に対応す
る記述モデル「分散集合オブジェクトモデル」を提案し実装した．これによっ
て，プログラマはデータの分散を意識せずにアルゴリズムを記述することがで
きる．プログラマはクラス定義の際に，オブジェクトを分割する$split()$, 
合併する$merge()$などを記述することで，メソッド呼び出し一つで計算への
参加・脱退が実現する．またアルゴリズムの記述においては，プログラマはデー
タとプロセッサの対応を意識する必要がない．

今後の課題としては，プリプロセッサによりメソッドが擬似的に返り値を取れ
るようにすることが挙げられる．現状の記述ではメソッドの実行を非同期的な
ものに限定しているので，メソッド呼び出しは返り値を取ることが出来ない．
これは，通常の同期的なメソッド呼び出しから機械的に変換できるものだと考
えている．このため，プログラマが通常のC/C++に近い文法で記述したプログ
ラムをプリプロセッサによって処理することで，より記述しやすいシステムを
構築していきたい．



\begin{thebibliography}{9}
\bibitem{mpi}
The Message Passing Interface(MPI). 　 http://www-unix.mcs.anl.gov/mpi/ .

\bibitem{corba}
Object Management Group.　　　　　　　　http://www.omg.org/ .

\bibitem{ca}
Andrew A. Chien, Vijay Karamcheti, John Plevyak, Xingbin Zbang .
 Concurrent Aggregates Language Report Version 2.0 

http://www-csag.ucsd.edu/papers/csag/external/ca-report.ps (1993)

\bibitem{phoenix}
Kenjiro Taura, Toshio Endo, Kenji Kaneda, and Akinori
Yonezawa. Phoenix : a Parallel Programming Model for Accommodating
Dynamically Joining/Leaving Resources. ACM SIGPLAN Symposium on
Principles and Practice of Parallel Programming (PPoPP 2003).

\bibitem{flick}
Eric Eide, Kevin Frei, Bryan Ford, Jay Lepreau, and Gary
Lindstrom. Flick: A flexible, optimizing IDL compiler. In
Proceedings of the ACM SIGPLAN '97 Conference on Programming
Language Design and Implementation (PLDI), pages 44-56, Las
Vegas, NV, June 1997. 

\bibitem{charm}
Charm++.

http://charm.cs.uiuc.edu/research/charm/


\end{thebibliography}

\end{document}
