\documentclass[12pt]{jarticle}
\IfFileExists{my.sty}{\usepackage{my}}{}
\IfFileExists{graphicx.sty}{\usepackage{graphicx}}{}
\IfFileExists{epsfig.sty}{\usepackage{epsfig}}{}
\title{OpenXM-RFC102 (Draft)}
\author{野呂 正行 \\ (神戸大理)}
\date{}
\begin{document}
\maketitle
\def\gr{Gr\"obner 基底}
\def\st{\, s.t. \,}
\def\noi{\noindent} 
\def\ve{\vfill\eject} 

\section{server 間通信の導入}

OpenXM-RFC-100, OpenXM-RFC-101 (以下 RFC-100,RFC-101) では, 計算は
client (master) と server 間の RPC (remote procedure call) として行われる. 
この形態で行うことができる分散並列計算としては

\begin{itemize}
\item master が仕事を分割して、各 server に依頼する.
\item 一つの計算にいくつか方法がある場合に, それぞれの方法を
別々の server に依頼する.
\end{itemize}

などが考えられ, 実際に有効であることを実証した \cite{OpenXM}.
しかし, さらに複雑な分散並列計算アルゴリズムでは,
server 間の通信が必要になる場合がある. 現状の RFC-100,101 でも,
server が tree 状に結合して分散計算を行うことはできるが,
この場合あくまで一方が client, 他方が server として動作している.
例えば, ScaLAPACK のように, 各 process が行列の
一部を保持して, 同一のプログラムを実行しながら LU 分解をして
いく, といった並列アルゴリズムを実装するのは難しい.
この場合, pivot 選択のために, 複数 process 間で保持されている
値の最大値を決定したり, 行の入れ換えを行ったりするために,
process 間でのデータのやりとりが必要となる. 

さらに単純な例としては broadcast がある. 例えば, ある多項式集合 $G$
がグレブナー基底かどうかチェックするには, $G$ から作られる全ての S-多項式が
$G$ により 0 に簡約されることを示せばよい。個々の簡約操作は独立なので,
適当に分割して並列計算できるが, まず $G$ を各 server に送る必要がある.
これは, RFC-100 のもとでは master が各 server に順に送るので, server の
数 $N$ に比例した手間がかかるが, server 間通信が使えれば, $\log N$ に
比例した手間で送ることもできる.

これらはごく限られた例であるが, 重要なことは, 
より高度な分散並列計算が実験できるような機能を提案し, 実装することである.
以下では MPI-2 で定義された動的プロセス生成, プロセスグループ間での
broadcast の仕様を参考に, OpenXM における server 間通信について
述べる.

\section{server の起動と server 間通信路の開設}

server は RFC-100, 101 により起動されるとする. server は起動された
時点では master との通信路のみを持つ. server-server 間の通信路は,
master から SM コマンドにより開設される. RFC-100, 101 では,
master-server 間の通信路は, server が起動した時点ですでに存在して
いたが, RFC-102 に対応するためには server が他のプロセスの
通信路を開設するための仕組みを実装している必要がある.

\begin{enumerate}
\item
\begin{verbatim}
SM_set_rank
\end{verbatim}

server 間の broadcast は, いくつかの server をグループ化して行うのが
自然である. 簡単のため, 各 server は, ただ一つのグループに属するとする.
master は, 各 server に, その server が属するグループのメンバーの総数
$nserver$ と, そのグループ内での識別子 $rank$ ($0\le rank \le nserver-1$)
を通知する.

Request:
\begin{tabular}{|c|c|}  \hline
{\tt int32 OX\_COMMAND} & {\tt int32 SM\_set\_rank} \\ \hline
{\tt int32 $nproc$} & {\tt int32 $rank$} \\
\hline
\end{tabular}

Output: none.

\item
\begin{verbatim}
SM_tcp_accept
\end{verbatim}

Request:
\begin{tabular}{|c|c|}  \hline
{\tt int32 OX\_COMMAND} & {\tt int32 SM\_accept} \\ \hline
{\tt int32 $port$} & {\tt int32 $peer$} \\
\hline
\end{tabular}

Stack after the request:
\begin{tabular}{|c|c|}  \hline
{\tt int32 OX\_DATA} & {\tt int32 $status$} \\
\hline
\end{tabular}

Output: none.

次項の {\tt SM\_tcp\_connect} とペアで, 既に存在している 2 つの server 
の間の TCP/IP による通信路を開設する. $port$ は, master が (ランダムに) 選んだ
TCP のポート番号である. このリクエストを受け取ると, server は, 
bind, listen, accept 動作を実行し, connect 待ち状態に入る. いずれかの動作
においてエラーを生じた場合には $status$ として $-1$, 成功した場合には
$0$ をスタックに置く. $peer$ は, 相手の server のグループ内での識別子
である.

\item
\begin{verbatim}
SM_tcp_connect
\end{verbatim}

Request:
\begin{tabular}{|c|c|}  \hline
{\tt int32 OX\_COMMAND} & {\tt int32 SM\_tcp\_connect} \\ \hline
{\tt int32 CMO\_String} & {$hostname$} \\ \hline
{\tt int32 $port$} & {\tt int32 $peer$} \\
\hline
\end{tabular}

Stack after the request:
\begin{tabular}{|c|c|}  \hline
{\tt int32 OX\_DATA} & {\tt int32 $status$} \\
\hline
\end{tabular}

Output: none.

前項の {\tt SM\_tcp\_accept} とペアで, 既に存在している 2 つの server
の間の TCP/IP による通信路を開設する. $host$ は相手の server が動作して
いるホスト名である. $host$ 上, ポート番号 $port$ で accept している server に対し,
connect する. 
エラーを生じた場合には $status$ として $-1$, 成功した場合には
$0$ をスタックに置く. $peer$ は, 相手の server のグループ内での識別子である.

\end{enumerate}

\section{server 間の通信}

RFC-102 下でのプログラミングスタイルは, 基本的には RFC-100,101 と変わらない.
すなわち, master であるプログラムが実行され, 必要に応じて server に
仕事が依頼され, master はその結果を使って自らの仕事を続行する.
これに加えて, RFC-102 では, server どうしが「自律的」にデータの送受信
を行うことができる. このため, server は, server 間通信路に CMO データを
送信する機能, また、server 間通信路から CMO データを受信する機能を
提供しなければならない. 通常, server は固有の言語を持つので, この機能
は server の組み込み関数として実現するのが自然であろう. 例えば {\tt asir}
({\tt ox\_asir}) の場合

\begin{enumerate}
\item {\tt ox\_send\_cmo\_102($Rank$,$Data$)}

識別子 $Rank$ の server に $Data$ を CMO として送信する.
\item {\tt ox\_recv\_cmo\_102($Rank$)}

識別子 $Rank$ の server から CMO データを受信する.
\end{enumerate}
として実現されている.

\subsection{broadcast}

server 間通信を利用する最も典型的な例として broadcast がある.

\begin{enumerate}
\item グループ内 broadcast

グループ内の broadcast は, いわゆる collective operation として実行さ
れる. すなわち, グループ内の各 server でそれぞれ独立に実行されているプ
ログラムにおいて, 一斉にある関数を呼び出すことにより, その関数から復帰
したときに, broadcast されたデータが返される, という形をとる. この場合
にデータの発信元 (root)の識別子は各 server があらかじめ知っておく必要がある.


\item master から server グループへの broadcast

master から server グループへの broadcast は, グループ内の
server がスタックコマンド待ち状態に行うことができるとする.
この場合, master はある一つの server に data を push する.
この server の識別子を $root$ とする.
その後, グループ内の全 server に, $root$ を発信元とする
broadcast を実行させるためのコマンドを逐次送信する.
\end{enumerate}

以下では, グループ内で broadcast を行う手続きを, MPI での実装に
したがって説明する. 簡単のため $root$ が $0$ であるとして,
識別子が $b2^k$ ($b$ は奇数) である server の動作を説明する.

\begin{enumerate}
\item 識別子が $(b-1)2^k$ である server からデータを受信する.
\item 識別子が $b2^k+2^i$ $(i=k-1,\ldots,0)$ の server にデータを送信する.
\end{enumerate}

この方法によれば, 
下位により長く連続して 0 が現われる識別子を持つ server ほど
先にデータを送信し始めるため, デッドロックにはならない. また,
独立なペアどうしの通信が同時に行えるとすれば, グループ内の
server の総数を $nserver$ とするとき, 高々 $\lceil \log_2 nserver\rceil$
ステップ後には全ての server にデータが行き渡る.




\section{エラー処理}

server は RFC-100,101 の リセットプロトコルを実装していれば,
master から server をリセットし, master-server 間の通信路を
リセットすることはできる. 

\section{API}


\end{document}