Return to OX-RFC-102.tex CVS log

Up to [local] / OpenXM / doc / OpenXM-specs

Annotation of OpenXM/doc/OpenXM-specs/OX-RFC-102.tex, Revision 1.6

1.1       noro        1: \documentclass[12pt]{jarticle}
                      2: \IfFileExists{my.sty}{\usepackage{my}}{}
                      3: \IfFileExists{graphicx.sty}{\usepackage{graphicx}}{}
                      4: \IfFileExists{epsfig.sty}{\usepackage{epsfig}}{}
                      5: \title{OpenXM-RFC102 (Draft)}
1.6     ! takayama    6: \author{野呂 正行 \\ (神戸大理)}
1.1       noro        7: \date{}
                      8: \begin{document}
                      9: \maketitle
1.6     ! takayama   10: \def\gr{Gr\"obner 基底}
1.1       noro       11: \def\st{\, s.t. \,}
                     12: \def\noi{\noindent}
                     13: \def\ve{\vfill\eject}
                     14:
1.6     ! takayama   15: \section{server 間通信の導入}
1.1       noro       16:
1.6     ! takayama   17: OpenXM-RFC-100, OpenXM-RFC-101 (以下 RFC-100,RFC-101) では, 計算は
        !            18: client (master) と server 間の RPC (remote procedure call) として行われる.
        !            19: この形態で行うことができる分散並列計算としては
1.1       noro       20:
                     21: \begin{itemize}
1.6     ! takayama   22: \item master が仕事を分割して、各 server に依頼する.
        !            23: \item 一つの計算にいくつか方法がある場合に, それぞれの方法を
        !            24: 別々の server に依頼する.
1.1       noro       25: \end{itemize}
                     26:
1.6     ! takayama   27: などが考えられ, 実際に有効であることを実証した \cite{OpenXM}.
        !            28: しかし, さらに複雑な分散並列計算アルゴリズムでは,
        !            29: server 間の通信が必要になる場合がある. 現状の RFC-100,101 でも,
        !            30: server が tree 状に結合して分散計算を行うことはできるが,
        !            31: この場合あくまで一方が client, 他方が server として動作している.
        !            32: 例えば, ScaLAPACK のように, 各 process が行列の
        !            33: 一部を保持して, 同一のプログラムを実行しながら LU 分解をして
        !            34: いく, といった並列アルゴリズムを実装するのは難しい.
        !            35: この場合, pivot 選択のために, 複数 process 間で保持されている
        !            36: 値の最大値を決定したり, 行の入れ換えを行ったりするために,
        !            37: process 間でのデータのやりとりが必要となる.
        !            38:
        !            39: さらに単純な例としては broadcast がある. 例えば, ある多項式集合 $G$
        !            40: がグレブナー基底かどうかチェックするには, $G$ から作られる全ての S-多項式が
        !            41: $G$ により 0 に簡約されることを示せばよい。個々の簡約操作は独立なので,
        !            42: 適当に分割して並列計算できるが, まず $G$ を各 server に送る必要がある.
        !            43: これは, RFC-100 のもとでは master が各 server に順に送るので, server の
        !            44: 数 $N$ に比例した手間がかかるが, server 間通信が使えれば, $\log N$ に
        !            45: 比例した手間で送ることもできる.
        !            46:
        !            47: これらはごく限られた例であるが, 重要なことは,
        !            48: より高度な分散並列計算が実験できるような機能を提案し, 実装することである.
        !            49: 以下では MPI-2 \cite{MPI2} で定義された動的プロセス生成, プロセスグループ間での
        !            50: broadcast の仕様を参考に, OpenXM における server 間通信について
        !            51: 述べる.
        !            52:
        !            53: \section{server の起動と server 間通信路の開設}
        !            54:
        !            55: server は RFC-100, 101 により起動されるとする. server は起動された
        !            56: 時点では master との通信路のみを持つ. server-server 間の通信路は,
        !            57: master から SM コマンドにより開設される. RFC-100, 101 では,
        !            58: master-server 間の通信路は, server が起動した時点ですでに存在して
        !            59: いたが, RFC-102 に対応するためには server が他のプロセスの
        !            60: 通信路を開設するための仕組みを実装している必要がある.
1.1       noro       61:
                     62: \begin{enumerate}
                     63: \item
                     64: \begin{verbatim}
1.3       noro       65: SM_set_rank_102
1.1       noro       66: \end{verbatim}
                     67:
1.6     ! takayama   68: server 間の broadcast は, いくつかの server をグループ化して行うのが
        !            69: 自然である. 簡単のため, 各 server は, ただ一つのグループに属するとする.
        !            70: master は, 各 server に, その server が属するグループのメンバーの総数
        !            71: $nserver$ と, そのグループ内での識別子 $rank$ ($0\le rank \le nserver-1$)
        !            72: を通知する.
1.1       noro       73:
                     74: Request:
                     75: \begin{tabular}{|c|c|}  \hline
1.3       noro       76: {\tt int32 OX\_COMMAND} & {\tt int32 SM\_set\_rank\_102} \\ \hline
1.2       noro       77: {\tt int32 $nserver$} & {\tt int32 $rank$} \\
1.1       noro       78: \hline
                     79: \end{tabular}
                     80:
                     81: Output: none.
                     82:
                     83: \item
                     84: \begin{verbatim}
1.3       noro       85: SM_tcp_accept_102
1.1       noro       86: \end{verbatim}
                     87:
                     88: Request:
                     89: \begin{tabular}{|c|c|}  \hline
1.3       noro       90: {\tt int32 OX\_COMMAND} & {\tt int32 SM\_accept\_102} \\ \hline
1.1       noro       91: {\tt int32 $port$} & {\tt int32 $peer$} \\
                     92: \hline
                     93: \end{tabular}
                     94:
                     95: Stack after the request:
                     96: \begin{tabular}{|c|c|}  \hline
                     97: {\tt int32 OX\_DATA} & {\tt int32 $status$} \\
                     98: \hline
                     99: \end{tabular}
                    100:
                    101: Output: none.
                    102:
1.6     ! takayama  103: 次項の {\tt SM\_tcp\_connect\_102} とペアで, 既に存在している 2 つの server
        !           104: の間の TCP/IP による通信路を開設する. $port$ は, master が (ランダムに) 選んだ
        !           105: TCP のポート番号である. このリクエストを受け取ると, server は,
        !           106: bind, listen, accept 動作を実行し, connect 待ち状態に入る. いずれかの動作
        !           107: においてエラーを生じた場合には $status$ として $-1$, 成功した場合には
        !           108: $0$ をスタックに置く. $peer$ は, 相手の server のグループ内での識別子
        !           109: である.
1.1       noro      110:
                    111: \item
                    112: \begin{verbatim}
1.3       noro      113: SM_tcp_connect_102
1.1       noro      114: \end{verbatim}
                    115:
                    116: Request:
                    117: \begin{tabular}{|c|c|}  \hline
1.3       noro      118: {\tt int32 OX\_COMMAND} & {\tt int32 SM\_tcp\_connect\_102} \\ \hline
1.1       noro      119: {\tt int32 CMO\_String} & {$hostname$} \\ \hline
                    120: {\tt int32 $port$} & {\tt int32 $peer$} \\
                    121: \hline
                    122: \end{tabular}
                    123:
                    124: Stack after the request:
                    125: \begin{tabular}{|c|c|}  \hline
                    126: {\tt int32 OX\_DATA} & {\tt int32 $status$} \\
                    127: \hline
                    128: \end{tabular}
                    129:
                    130: Output: none.
                    131:
1.6     ! takayama  132: 前項の {\tt SM\_tcp\_accept\_102} とペアで, 既に存在している 2 つの server
        !           133: の間の TCP/IP による通信路を開設する. $host$ は相手の server が動作して
        !           134: いるホスト名である. $host$ 上, ポート番号 $port$ で accept している server に対し,
        !           135: connect する.
        !           136: エラーを生じた場合には $status$ として $-1$, 成功した場合には
        !           137: $0$ をスタックに置く. $peer$ は, 相手の server のグループ内での識別子である.
1.1       noro      138:
                    139: \end{enumerate}
                    140:
1.6     ! takayama  141: \section{server 間の通信, broadcast および reduction}
1.1       noro      142:
1.6     ! takayama  143: RFC-102 下でのプログラミングスタイルは, 基本的には RFC-100,101 と変わらない.
        !           144: すなわち, master であるプログラムが実行され, 必要に応じて server に
        !           145: 仕事が依頼され, master はその結果を使って自らの仕事を続行する.
        !           146: これに加えて, RFC-102 では, server どうしが「自律的」にデータの送受信
        !           147: を行うことができる. このため, server は, server 間通信路に OX データを
        !           148: 送信する機能, また、server 間通信路から OX データを受信する機能を
        !           149: 提供しなければならない.
1.1       noro      150:
1.6     ! takayama  151: server 間通信を利用する最も典型的な例として broadcast がある.
1.1       noro      152:
                    153: \begin{enumerate}
1.6     ! takayama  154: \item グループ内 broadcast
1.1       noro      155:
1.6     ! takayama  156: グループ内の broadcast は, いわゆる collective operation として実行さ
        !           157: れる. すなわち, グループ内の各 server でそれぞれ独立に実行されているプ
        !           158: ログラムにおいて, 一斉にある関数を呼び出すことにより, その関数から復帰
        !           159: したときに, broadcast されたデータが返される, という形をとる. この場合
        !           160: にデータの発信元 (root)の識別子は各 server があらかじめ知っておく必要がある.
        !           161:
        !           162: \item master から server グループへの broadcast
        !           163:
        !           164: master から server グループへの broadcast は, グループ内の
        !           165: server がスタックコマンド待ち状態に行うことができるとする.
        !           166: この場合, master はある一つの server に data を push する.
        !           167: この server の識別子を $root$ とする.
        !           168: その後, グループ内の全 server に, $root$ を発信元とする
        !           169: broadcast を実行させるためのコマンドを逐次送信する.
1.1       noro      170: \end{enumerate}
                    171:
1.6     ! takayama  172: 以下では, グループ内で broadcast を行う手続きを, MPI での実装に
        !           173: したがって説明する. 簡単のため $root$ が $0$ であるとして,
        !           174: 識別子が $b2^k$ ($b$ は奇数) である server の動作を説明する.
1.1       noro      175:
                    176: \begin{enumerate}
1.6     ! takayama  177: \item 識別子が $(b-1)2^k$ である server からデータを受信する.
        !           178: \item 識別子が $b2^k+2^i$ $(i=k-1,\ldots,0)$ の server にデータを送信する.
1.1       noro      179: \end{enumerate}
                    180:
1.6     ! takayama  181: この方法によれば,
        !           182: 下位により長く連続して 0 が現われる識別子を持つ server ほど
        !           183: 先にデータを送信し始めるため, デッドロックにはならない. また,
        !           184: 独立なペアどうしの通信が同時に行えるとすれば, グループ内の
        !           185: server の総数を $nserver$ とするとき, 高々 $\lceil \log_2 nserver\rceil$
        !           186: ステップ後には全ての server にデータが行き渡る.
1.1       noro      187:
1.6     ! takayama  188: 以下に, {\tt ox\_asir} における実装を示す.
1.4       noro      189:
                    190: \begin{verbatim}
1.5       noro      191: void ox_bcast_102(int root)
1.4       noro      192: {
                    193:     Obj data;
                    194:     int r,mask,id,src,dst;
                    195:
                    196:     r = myrank_102-root;
1.5       noro      197:     if ( r == 0 )
                    198:         data = (Obj)asir_pop_one();
1.4       noro      199:     if ( r < 0 ) r += nserver_102;
                    200:     for ( mask = 1; mask < nserver_102; mask <<= 1 )
                    201:         if ( r&mask ) {
                    202:             src = myrank_102-mask;
                    203:             if ( src < 0 ) src += nserver_102;
                    204:             ox_recv_102(src,&id,&data);
                    205:             break;
                    206:         }
                    207:     for ( mask >>= 1; mask > 0; mask >>= 1 )
                    208:         if ( (r+mask) < nserver_102 ) {
                    209:             dst = myrank_102+mask;
                    210:             if ( dst >= nserver_102 ) dst -= nserver_102;
                    211:             ox_send_data_102(dst,data);
                    212:         }
1.5       noro      213:     asir_push_one(data);
1.4       noro      214: }
                    215: \end{verbatim}
                    216:
1.6     ! takayama  217: 同様の手続きに reduction がある. これは, 各 server にあるデータを, 2
        !           218: 項演算により処理していき, 最後に $root$ に演算結果が集められる手続きで
        !           219: ある.  この場合も, 簡単のため $root$ が $0$ であるとして, 識別子が
        !           220: 識別子が $b$ の server では, $b$ を下位ビットから順に見て,
1.4       noro      221:
                    222: \begin{enumerate}
1.6     ! takayama  223: \item そのビットが 1 なら, そのビットを 0 にした識別子をもつ server
        !           224: (それは必ず存在する) にデータを送信して終了.
        !           225: \item そのビットが 0 で, そのビットを 1 にした値が $nserver-1$ 以下
        !           226: なら, そこからデータを受信する. そのデータと手持ちのデータ
        !           227: の 2 項演算結果で手持ちデータを更新する.
1.4       noro      228: \end{enumerate}
                    229:
1.6     ! takayama  230: この方法によれば, 最終結果は $root$ にデータが集められる. この場合にも,
        !           231: server の総数を $nserver$ とするとき, 高々 $\lceil \log_2 nserver\rceil$
        !           232: ステップ後には手続きが終了する.
1.4       noro      233:
                    234: \begin{verbatim}
1.5       noro      235: void ox_reduce_102(int root,void (*func)())
1.4       noro      236: {
1.5       noro      237:     Obj data,data0,t;
1.4       noro      238:     int r,mask,id,src,dst;
                    239:
                    240:     r = myrank_102-root;
                    241:     if ( r < 0 ) r += nserver_102;
1.5       noro      242:     data = (Obj)asir_pop_one();
1.4       noro      243:     for ( mask = 1; mask < nserver_102; mask <<= 1 )
                    244:         if ( r&mask ) {
                    245:             dst = (r-mask)+root;
                    246:             if ( dst >= nserver_102 ) dst -= nserver_102;
                    247:             ox_send_data_102(dst,data);
                    248:             break;
                    249:         } else {
                    250:             src = r+mask;
                    251:             if ( src < nserver_102 ) {
                    252:                 src += root;
                    253:                 if ( src >= nserver_102 ) src -= nserver_102;
                    254:                 ox_recv_102(src,&id,&data0);
                    255:                 (*func)(CO,data,data0,&t); data = t;
                    256:             }
                    257:         }
1.5       noro      258:     asir_push_one(r?0:data);
1.4       noro      259: }
                    260: \end{verbatim}
                    261:
1.6     ! takayama  262: 対応する SM コマンドは以下の通りである.
1.5       noro      263:
                    264: \begin{enumerate}
                    265: \item
                    266: \begin{verbatim}
                    267: SM_bcast_102
                    268: \end{verbatim}
                    269:
                    270: Request:
                    271: \begin{tabular}{|c|c|c|} \hline
                    272: {\tt int32 OX\_COMMAND} & {\tt int32 SM\_bcast\_102} & {\tt int32 $root$} \\ \hline
                    273: \end{tabular}
                    274:
                    275: Output: none.
                    276:
                    277: Stack after the request:
                    278: \begin{tabular}{|c|c|}  \hline
                    279: {\tt int32 OX\_DATA} & {\tt $CMObject$} \\ \hline
                    280: \end{tabular}
                    281:
                    282: \item
                    283: \begin{verbatim}
                    284: SM_reduce_102
                    285: \end{verbatim}
                    286:
                    287: Request:
                    288: \begin{tabular}{|c|c|}  \hline
                    289: {\tt int32 OX\_COMMAND} & {\tt int32 SM\_reduce\_102} \\ \hline
                    290: {\tt int32 $root$} & {\tt int32 CMO\_String} {$opname$} \\ \hline
                    291: \end{tabular}
                    292:
                    293: Stack after the request:
                    294: \begin{tabular}{|c|c|}  \hline
                    295: {\tt int32 OX\_DATA} & {\tt $CMObject$} \\ \hline
                    296: \end{tabular}
                    297:
                    298: Output: none.
                    299: \end{enumerate}
1.4       noro      300:
1.6     ! takayama  301: \section{エラー処理}
1.1       noro      302:
1.6     ! takayama  303: server は RFC-100,101 の リセットプロトコルを実装していれば,
        !           304: master から server をリセットし, master-server 間の通信路を
        !           305: リセットすることはできる. これに加えて,グループ内の server 間通信路
        !           306: をリセットする必要がある. 識別子が $i$ ($0\le i \le nserver$)
        !           307: の server の動作は次のようになる.
1.1       noro      308:
1.2       noro      309: \begin{tabbing}
1.6     ! takayama  310: \underline{識別子が $i$ ($0\le i \le nserver$) の server の動作}\\
1.2       noro      311: for \= $j = 0$ \= to $i-1$ do\\
                    312:     \> do\\
1.6     ! takayama  313:     \>         \>$data$ $\leftarrow$ 識別子 $j$ の server からの OX データ\\
1.2       noro      314:     \> while $data \neq$ {\tt OX\_SYNC\_BALL}\\
                    315: end for\\
                    316: for $j = i+1$ to $nserver-1$ do\\
1.6     ! takayama  317:     \> {\tt OX\_SYNC\_BALL} を 識別子 $j$ の server に送信\\
1.2       noro      318: end for
                    319: \end{tabbing}
1.6     ! takayama  320: この手順により, デッドロックなしに全ての通信路を空にすることができる.
        !           321: この操作は, master-server 通信路のリセット後に行われるため, 各 server
        !           322: は master からのデータ待ち状態にある. よって, 次の SM コマンドを
        !           323: 各 server に一斉に送ることにより行う.
1.3       noro      324:
                    325: \begin{verbatim}
                    326: SM_reset_102
                    327: \end{verbatim}
                    328:
                    329: Request:
                    330: \begin{tabular}{|c|c|}  \hline
                    331: {\tt int32 OX\_COMMAND} & {\tt int32 SM\_reset\_102} \\ \hline
                    332: \end{tabular}
                    333:
                    334: Output: none.
                    335:
1.1       noro      336: \section{API}
1.2       noro      337:
1.6     ! takayama  338: 以下, asir における RFC-102 関連の API を紹介する.
1.2       noro      339:
1.6     ! takayama  340: \subsection{server 間通信路開設}
1.2       noro      341:
1.6     ! takayama  342: 以下の関数は, master 用に用意されたもので, SM コマンド送信用の
        !           343: wrapper である.
1.4       noro      344:
1.2       noro      345: \begin{itemize}
1.3       noro      346: \item {\tt ox\_set\_rank\_102($Server$,$Nserver$,$Rank$)}
1.2       noro      347:
1.6     ! takayama  348: $Server$ が属するグループに属する server の総数 $Nserver$ と,
        !           349: その server のグループ内識別子 $Rank$ を通知する.
1.2       noro      350:
1.4       noro      351: \item {\tt ox\_tcp\_accept\_102($Server$,$Port$,$Rank$)}
1.2       noro      352:
1.6     ! takayama  353: $Server$ に対し, ポート番号 $Port$ で,
        !           354: 識別子 $Rank$ の server からの connect 待ち状態に入るよう指示する.
        !           355: 通信が成立したら, 送受信バッファのセットアップ,
        !           356: 相手先テーブルへの登録などを行う.
1.2       noro      357:
1.4       noro      358: \item {\tt ox\_tcp\_connect\_102($Server$,$Host$,$Port$,$Rank$)}
1.2       noro      359:
1.6     ! takayama  360: $Server$ に対し, ホスト名 $Host$ のポート番号 $Port$ の TCP ポートに対して
        !           361: connect するよう指示する.
        !           362: 通信が成立したら, 送受信バッファのセットアップ, 相手を $Rank$ として
        !           363: 相手先テーブルへの登録などを行う.
1.4       noro      364:
                    365: \item {\tt ox\_reset\_102($Server$)}
                    366:
1.6     ! takayama  367: $Server$ に対し通信路リセット動作を指示する. この操作は, グループ内全ての server
        !           368: で行われなければならない.
1.2       noro      369: \end{itemize}
                    370:
1.6     ! takayama  371: \subsection{server 間通信}
1.2       noro      372:
                    373: \begin{itemize}
1.3       noro      374: \item {\tt ox\_send\_102($Rank$,$Data$)}
1.2       noro      375:
1.6     ! takayama  376: 識別子 $Rank$ の server に $Data$ を OX データとして送信する.
        !           377: 識別子 $Rank$ の server は対応する受信を開始しなければならない.
1.2       noro      378:
1.3       noro      379: \item {\tt ox\_recv\_102($Rank$)}
1.2       noro      380:
1.6     ! takayama  381: 識別子 $Rank$ の server から OX データを受信する.
        !           382: 識別子 $Rank$ の server は対応する送信を開始しなければならない.
1.2       noro      383:
1.5       noro      384: \item {\tt ox\_bcast\_102($Root$[,$Data$])}
                    385:
1.6     ! takayama  386: 識別子 $Root$ の server を root として, グループ内で broadcast する.
        !           387: $Data$ が指定された場合, スタックにプッシュされる.
        !           388: を指定する必要がある. 識別子が $Root$ に等しい server で, スタック
        !           389: からデータがポップされ, そのデータが, 各呼び出しの戻り値となる.
1.5       noro      390:
                    391: \item {\tt ox\_reduce\_102($Root$,$Operation$[,$Data$])}
                    392:
1.6     ! takayama  393: グループ内の各 server のスタックからポップしたデータに対し
        !           394: $Operation$ で指定される二項演算を行い,
        !           395: 結果を $Root$ で指定される server での関数呼び出しの戻り値として
        !           396: 返す.
        !           397: $Data$ が指定された場合, スタックにプッシュしてから上記の操作を
        !           398: 実行する. $Root$ 以外の server での戻り値は 0 である.
1.2       noro      399:
                    400: \end{itemize}
1.1       noro      401:
1.4       noro      402: \begin{thebibliography}{99}
                    403: \bibitem{OpenXM}
                    404: Maekawa, M. et al, The Design and Implementation of OpenXM-RFC 100 and 101.
                    405: Proceedings of ASCM2001, World Scientific, 102-111 (2001).
                    406: \bibitem{MPI2}
                    407: Gropp, W., et al, Using MPI-2 Advanced Features of the Message-Passing
                    408: Interface. The MIT Press (1999).
                    409: \end{thebibliography}
1.1       noro      410: \end{document}