INDEX

分散処理網を想定し， 情報の伝送コストを最小とするジョブの処理ホスト決定アルゴリズムを検討した。

ジョブの処理に必要な情報をジョブトランザクションＲ，アプリケーションプログラムＰ， データＤの三者と考え，ジョブを図１のようなサブジョブの直列処理要求とし， 目的関数は伝送コスト，即ち距離及び情報量に比例すると仮定する。 なお，ディレクトリ問題，処理コストは考えない。

１つのホストにＲＰＤ三者が同時に存在しない場合， サブジョブの処理ホストをいずれに選んでも情報の伝送を行わねばならないが， どの情報の伝送を許すかにより基本的には (A)渡り歩き方式（Ｐを保持するホストを処理ホストとする） (B)呼び寄せ方式（Ｒを保持するホストを処理ホストとする） (C)適応方式（ＲＰＤ共に伝送を許し，最も有利と考えられるホストを処理ホストとする） が考えられる。

(C)による最適解はダイナミックプログラミング(DP)により求められるが， 計算が複雑であるので簡易手法(C1)１段推定法を提案する。 これは，あるサブジョブを処理したホストからみて 伝送コストが最小となるように次のサブジョブの処理ホストを決定するもので， 最後のサブジョブの処理ホストは端末の位置も考慮して決定するようにしている。

ジョブはサブジョブ（ＲＰ各１個とＤ２個を必要とする）の10段で， |R_i|=|D_ij|=1，|P_i|=k（ｋはＰとＤの大きさの比）とし， 図２に示す６種類の網について，ＰＤが網内一様分散の場合の(A)(B)(C1)の伝送コスト， 及び(DP)の最小伝送コストを計算とシミュレーションにより （但し(DP)はシミュレーションのみ）求めた。 計算結果は図３のとおりである。 (DP)を基準にした(C1)のコスト増は網形態にはあまり影響されず同じような特性を示し， 高々7％である。

ここには結果を示していないが， 梯子形網のノード数を増やした場合，ジョブに必要なＤの数を変えた場合， 端末に近いノードほどＰＤが存在する確率が大きい場合も検討した。 図３と同様な特性を示したので，一般に１段推定法で十分であるといえる。

"On Job Allocation Algorithms in Distributed Processing Networks", IMS XXIV, Hawaii, June 21, 1979, H.Sanada & Y. Tezuka.