P6 P0 Fat lines are the execution
4.2 木構造ネット ワーク
Size of facility: p 0 logn n n=2
(no cility)
Mean cost logn logn0loglogn logn=2 1
for communication
Maximum cost 2logn 2(logn0loglogn) logn 2
for communication
表 4.1: 頂点数nの平衡二分木上に木形状設備を配置した場合の通信コスト
一般に低次ネットワークが用いられるので，各点の次数を制限した場合について議論する．
通信システムの構築コストは設備サイズで表し，サイズを指定した木形状設備の最適配 置により通信システムを構築する．また，超並列・分散計算機システムの通信は多対多で 行われる場合が多い．そこで，設備配置の評価指標に平均通信コストを用いる．本章では，
木形状設備の構築コストを小さくするために小サイズの部分設備を用いた木形状設備の最 適配置問題について検討する．具体的には，頂点数nで次数がO(logn=loglogn)である木 構造ネットワーク上への等分割可能な木形状設備の配置について議論する．また，複数の 通信に対応するために複数個の木形状設備を重ねずに配置する複数設備配置問題について 検討する．具体的には，頂点数n で次数がO(logn=loglogn)であるバンド 幅1の木構造 ネットワーク上への複数個の木形状設備の配置について議論する．
次節では，木構造の通信ネットワークに対する木形状の高速通信路設備配置の有用性に ついて議論する．
Optimal facility F
Low-speed network e
e e e
e e e e
1
2 3
4
5 6
8 7
図 4.1: 平衡二分木上の最適な設備F
な木形状設備とよぶ．平衡二分木に対する最適な設備は，根が中心となる平衡二分木であ る．このとき，通信ネットワークの平均および最大通信コストは設備の距離和および偏差 のそれぞれほぼ倍となる．また，設備を配置しない場合の通信ネットワークの平均および 最大通信コストは，サイズ0の最適な木形状設備を配置した場合の距離和および偏差のそ れぞれほぼ倍となる．
図4.1に，頂点数31の平衡二分木とサイズ6の最適な木形状設備Fを示す．配置する設 備のサイズを増加させることにより，通信ネットワークの通信コストを削減できる．たと えば，図4.1に対するサイズ14の最適な木形状設備F0は，図のFに辺e1〜e8を追加したも のであるが，F0の距離和と偏差はFの場合のほぼ半分になり，通信ネットワークの平均お よび最大通信コストは半減する．表4.1に，頂点数nの平衡二分木上にサイズpの設備を 配置した場合の通信ネットワークの平均および最大通信コストの概数を示す．たとえばサ イズ
p
nの設備を用いることにより，設備のない場合に比べ，通信ネットワークの平均およ び最大通信コストを半減できる．
Size of 0 logn n n=2
facility: p (nofacility)
Construction n01 (n01)+(logn (n01)+( p
n (n01)+(n=2
cost +1)(logn+2)=2 +1)(
p
n+2)=2 +1)(n=2+2)=2
表 4.2: 頂点数nの平衡二分木上に完全ネットワークによる設備を配置した場合の構築コ スト
4.2.2
設備サイズと構築コスト
設備サイズと構築コストとの関係について議論する．
図4.2に，設備Fの完全ネットワークを用いた実装を示す．設備を完全ネットワークを用 いて実装する場合，設備内の通信は設備の各二点間でダ イレクトに行うことから，低コス トの通信路を用いることができる．したがって，設備のサイズ単位あたりの構築コストは 低い．しかし，サイズpの設備の構築にp+1C2個の通信路が必要なので，設備サイズに対す る構築コスト増加はO(p2)と大きい．一方，設備を一つのブロードキャスト通信路を用い て実装する場合，多対多通信やコリジョン対策が必要なことから，高コストの通信路が必 要である．したがって，設備のサイズ単位あたりの構築コストは高い．しかし，設備サイ ズに対する構築コスト増加はO(p)と小さい．
低速通信路を用いた完全ネット ワークにより構築するサイズ p の設備の構築コストは
(p+1)(p+2)=2である．すなわち，配置する設備のサイズ増加により，通信ネットワーク の構築コストは増加する．表4.2に，サイズpの設備の構築コストの概数を示す．たとえば サイズ
p
nの設備の構築コストが，およそn=2になることがわかる．
なお，ブロード キャスト通信路のサイズ単位あたりのコストをpn=2以下に抑えること ができれば，サイズpnの設備の構築コストを更に低減である．
4.2.3
実用的な設備の配置
頂点数 nの平衡二分木ネットワークにサイズ
p
nの設備を付加することにより，従来の
1.5倍の構築コストで通信コストを半減できることが分る．
しかし，実用性の観点では，実際の通信ネットワークシステム構築において改良すべき 点がある．以下に，木形状設備の問題点と，その対策を示す．
Facility F is constracted by a complete interconnection with low-speed network.
F
図 4.2: 完全ネットワークによる設備を配置した平衡二分木ネットワーク
（１）設備の構築コスト の低減
一般に，高速通信路設備を用いて通信ネットワークの高速化を行うには，膨大なコスト が必要になる．そこで，小サイズの高速通信路設備を複数個用いて通信ネットワークを構 築することにより，コストを抑えつつ高速化を行うことが期待されている．また，量産効 果を考慮すると，同一サイズの高速通信路設備のみを用いてネットワークを構築すること は，コスト低減に有用である．
たとえば，サイズp=2の部分設備を完全ネットワークで構築すると，その構築コストは
(p=2+1)(p=2+2)=2となる．よって，サイズp=2 の部分設備を二つ用いて設備を構築し
た場合，設備の構築コストは(p=2+1)(p=2+2)となる．これは，完全ネットワークによる サイズpの設備の構築コスト(p+1)(p+2)=2のおよそ半分である．この例として図4.3を
示す．図4.3(a)の設備サイズは6なので，設備の構築コストは21である．図4.3(b)のよ
うにサイズ3の部分設備を二つ用いて設備を構築した場合，設備の構築コストは12とほぼ 半減する．
しかし，同一サイズの設備を木構造ネットワーク上に配置することは，今まで十分に研
Facility F consists of 21 lines.
Facility F
Subfacility
Facility F consists of 12 lines.
Facility F
(a) Facilityconsistsof completeconnections. (b) Facilityconsistsof twosubfacilities.
図 4.3: 部分設備による構築コスト削減 究されていない．
（２）複数の通信要求への対応
一つの高速通信路設備を配置した通信ネットワークは，同時に一つの通信しか高速化で きない．一般に，複数の通信を同時に行う場合が多いので，一つの高速通信路設備を用い たシステムの性能向上は不十分な場合がある．そこで，複数個の高速通信路設備を配置し，
一つの通信が一つの設備のみ使用するようルーティングすることにより，通信量の多いシ ステムにおいても十分な性能向上が期待できる．また，量産効果を考慮すると，同一サイ ズの高速通信路設備のみを用いてネットワークを構築することは，コスト低減に有用であ る．この例を図4.4に示す．図4.4(a)は一つの設備を配置した場合である．通信1と通信2 が同時に行われるとき，通信1の通信コストは2になるが，通信2は設備を使用できず通 信コスト6になる．そして，この通信2の通信コストがシステム全体の実行時間に影響す る場合がある．図4.4(b)のように設備二つを用いることにより，通信1と通信2の通信コ ストをともに4にすることができる．
しかし，同一サイズの設備を木構造ネットワーク上に複数個配置することは，今まで十 分に研究されていない．
Comm.1 uses facility F.
Facility F
Comm.2 can’t use facility F.
2 hop
6 hop
2
Facility F 1 Comm.1 uses facility F . 1
2
4 hop
4 hop
Comm.2 uses facility F . Facility F
(a)Communicationsusing facility. (b) Communicationsusing two facilies.
図 4.4: 複数個の設備による通信コスト削減
4.2.4
まとめ
本節では，平衡二分木における設備配置について議論し，木形状設備を配置することに より低速通信路と高速通信路の混在する低コストで高性能な木構造通信ネットワークシス テムを構築できることを明らかにした．実用性の観点から，実際に通信ネットワークシス テムを構築する問題点について検討し，同一サイズの部分設備で構成される設備配置問題 や，同一サイズの複数個の設備の配置問題が重要であることを示した．
以下の節では，通信ネットワークにこれらの実用的設備を配置する方法について議論する．