高並列計算機ハードウェア構成法の研究

九州大学学術情報リポジトリ

Kyushu University Institutional Repository

高並列計算機ハードウェア構成法の研究

石川, 勉

https://doi.org/10.11501/3052535

出版情報：Kyushu University, 1990, 工学博士, 論文博士 バージョン：

権利関係：

5 ̲  2 

言吉イ言束頁イヒの主三芸芸言果是菖

高並列計算機を実現する場合、信頼性に関しては、

i )問題求解中に故障しないか，あるいは故障する場合にはそれに対応できること。

註)人手が介在する保守の周期が現実的な時間であること。

出)実用的な稼働率が得られること。

が必要な条件となる。これらの条件から、高信頼化のため冗長構成を適用する場合の基本 的な課題について考察する。

なお、以後で用いる用語について、

MTBF

，

MTTR

はそれぞれ平均故障間隔，故障 を検出し予備と切り替えるシステム再構成時間と、

MTTF

は予備が無くなりシステム再 構成が不能になるまでの時間と定義する。また、故障は偶発故障を想定し信頼度関数とし ては指数関数を用いることとする。

( 1 )問題求解中の故障

PE 

性能:p， 

P  E

故障率 :A， 

P  E

数 :

N

，の計算機で規模Qの問題を解く場合、求 解中に計算機の故障する確率Sは

S 

= 

1 ‑

e x p   (‑

A c T)  ( 5.  1)  ここで、 Ac 計算機の故障率(ニNA) 

T 求解に要する時間

(=Q/N

P) 

で与えられる。

問題規模Qとして

10 

1 

3 F l o p ( F l o a t i n g  p o i n t   O p e r a t i o n )

程度、

1 L  S  1

化された

PE

が開発されつつある10) ことから、 A

=  1  0 

2 ‑‑‑‑

1  0  3 

f 

i  t

， P 

=  O .   1  ‑ ‑ ‑ ‑10M F  1 

0 

p 

s程 度を想定すると、

S

は、

O .0 0 0 0 3  ‑ ‑ ‑ ‑ 0 .  0 3  

となる。すなわち、このような巨大計算におい ても求解中に故障する確率は均 Oであり、これについてはほとんど問題にならないと言え る。

‑ 6 2 ‑

( 2 )人手が介在する保守の周期 T~，

故障が発生するごとに人手によりこれを修復する場合には“保守周期 T~

=MTBF" 

と考えてよく、

PE

数が多い場合には前述したように時間オーダでの保守が必要になる。

従って、 u)の条件を満たすためには故障の検出から予備との切替えまでを全て自動化す ること、すなわちシステム再構成の自動化が必要になる。この自動化が実現できれば、 T

M=MTTF

にでき、

MTTF

の向上が次の課題となる。

MTTF

は冗長構成の適用によ り向上するが、その向上度はその適用法に大きく依存する。例えば計算機ごとに二重化し ても

MTTF

は高々1.

5

倍しか向上しない。また、冗長度(予備部分/有効部分)を高め れば一般に

MTTF

の向上度は高まるが、経済性の点から現実的とは言えない。従って、

少ない冗長度で

MTTF

を向上できる効果的な冗長構成の適用が課題となる。

( 3 )稼働率

: α

計算機が実用的であるためには稼働率αが lに近いことが必要である。このためにはM

TTF

の間で考えれば、

α=MTBF/(MTBF+MTTR)

であるから、

MTBF

を 向上させるか，

MTTR

を減少させる必要がある。

MTBF

を向上させるには高信頼な部 品を用いるか，故障をマスクできる

TMR ( T r i p l e  M o d u l a r  R e d u n d a n c y  

，この場合、

M

TTF=MTBF

であり、

α=1 

)あるいは

H y b r i dR e d u n da n c y

^l21)等の冗長構成を採る ことが考えられるが、一般に前者の場合には部品価格が高くなることから，また、後者の 場合には冗長度，金物量が大幅に増加することから共に経済的に不利である。

他方、

MTTR

は故障を検出する時間

( t D )

と故障部分を予備と切り替える時間

( t s )

の和であり、前述のシステム再構成の自動化が可能となれば

t s

^与

O

となり、

t D

が大きな 割合を占めるようになる。

t D

は故障の検出が一般に各構成部分の診断により行われるこ とから、この診断時間の総和であり、例えば計算機外に診断機能を設け、これにより

PE

ごとに診断するような場合を想定すると、

t D =Nto ( t o :   PE

の診断時間)となる。こ の場合

α

は、

MTBF=l/NA

であるから(次節の(

5 .   3 )

式を参照)、

α

ー (

1  /N 

A) / 

( 1  /N 

A 

+  N  t 

0 ) 

=  1  / ( 1  +  N 

2 A 

t 

0)  ( 5.  2) 

となり、

PE

数

N

が大きくなると急激に低下する。例えば、え=

1  0 

3 f i  ，1 t 0 

=  1 

s 

e c  

のとき、

N =  1  0

⁴では

α= 0 . 9 7

となるが、

N= 1  0 

6 では

α= 0 . 0 0 4

となってしまう。

‑63‑

従って、高並列計算機においてはtDがNに比例しない診断の並列化が必須の条件となる。

以上から高並列計算機の高信頼化のための基本的課題は、現実的な保守周期、経済性、

稼働率の観点から、イ)少ない冗長度でMTTFを向上できる効果的冗長構成、ロ)シス テム再構成の自動化とその場合の診断の並列化、となる。

‑ 6 4 ‑

5 ̲  3 

妻事ヌド白勺ア亡主主と;f毒圧支え車用 Cこ よ る 交 力 主 畏

本節では基本的な冗長方式をPE毎に適用した場合の MTTF向上効果を解析的に明ら かにするとともに、各方式毎の PE数と MTTF向上度の関係の近似式を与える。又、 P

E内に誤り訂正機能を適用した場合の MTTF向上効果についても明らかにする。

5.  3.  1 多重化、 n

+ 

1予備によるMTTFの向上

冗長構成の適用による高信頼化は、基本的に切替単位が小さい程効果的であり、並列計 算機ではこれを容易にPEレベルまで小さくできる。このことは単一計算機に比べ、高信 頼化上非常に有利な点である。

従って、ここでは並列計算機構造を特定せず、最も一般的な冗長方式であるn重化、 n

+ 

1予備の各方式をPE単位に適用した場合の効果、具体的には次のように定義する M T T F向上度 G、

G =  (元長化した計算機の MTTF)/(冗長化しない計算機の MTTF)

を明らかにする。なお、算出にあたっては故障PEは瞬時に切替わるものとする。

図5. 1 1こMTTFの算出モデルを示す。 n重化の場合、 l台の PEにn‑1台の予備 を設け、これをN組用いPE数Nの計算機を構成する。また、 n

+ 

1予備の場合にはn台 のPEに l台の予備を設け、これを N/n組用いる。

MTTFは、

(100 

M  T  T  F  = 

J 0 

R  ( t ) d  t 

( 5.  3)  ここで、 R(t) :計算機の信頼度関数

で表されるためMTTF向上度 Gは

G=f 了 R ( t ) d t/ 

(1 

/ N  

A)  ( 5.  4)  となる。また、 R(t)は、切替回路の故障を無視すると以下で与えられる。

‑65‑

N  N/n 

n 

可1 11

ノ1LIli‑‑Tl

陀

Sp

a r e  

陀

5  ) 

6 )  ( 5 . 

( 5 . 

~/n d t  ここで、r(t):PEの信頼度関数(ニexp(‑).t))

(1‑r(1))  n} ='  dt 

(n 

+ 

1) r(t)n  (1 ‑r(t)) } 

」ー

n重 化 :R (t) 

n十 l予 備 :R (t) 

n  o u t   o f   n + 1  

b)  n plex 

N)>nの場合 6 )式により求まるが、高並列計算機すなわち、

(導出は付録 l参照)。

を想定すると以下の近似式が成り立つ 3) ，.....，  (5. 

G は (5 . 

MTTF算出モデル 図5. 

7 )  ( 5 •

G~N ト I/n

n重 化

8 )  ( 5 .  G^与 N^1/2 

/n 

n 

+ 

1予 備 :

N

^{1‑ 1/ n}  

'T

n u  

p +  

o  l  

VA 戸 ︼

+L

I i u   n H n u  

門川

nH

r‑

‑J Il tk  

即ち、 MTTF向上度GはPE数Nと多重度等の冗長構成ノfラメータ nの単純な式で近似

= 1 0  

きることになる。従って、高並列計算機ではPEを切替単位とする冗長構成は極めて効果

η = 4  

1 0 4 

(N/n)'/2  できることになる。

1 0³ 

(9 

HC ωE ω

﹀O﹂QE

一 6 

)式による厳密な計算値、破

5 )

， 

( 5 .  

2に両方式の Gを 示 す 。 実 線 が (5 . 

図5.

8 )式の近似値である。同図から、近似値による誤差が比較的少な

7)

， 

( 5 .  

線 が (5 . 

これら冗長化によりMTTFを数桁向上で PE数が多い場合には、

いことが分かる。又、

nH U 

AHV 

4冒

EE

‑‑

︐

一 一

︐aE・E

・

︐

fT n u    

J P

守1︐

n u  J + ' E・

J H U  

7vO J

n 

︐n

k 

1 0

² 

hL

ト

2

ト

P  台を用いた並列計算機において、

10³ fitの PE 1 0 6 

きることがわかる。例えば、

G ~ 1000となり、 MTTFを 1時間から1000時間に向上で Eごとの 2重化を行った場合、

図

5 .

1 0

⁶  1 0⁵ 

N 

n+l予備によるMTTFの向上

‑67‑ 1 0⁴ 

N u m b e r   o f   P E s  

1 0³ 

10² 

n重化，

2 

1 0  

予備を適用した計算機全体ではその故障率はN).  ⁵となる。一方、計算機の等価的な故障 n重化あるいはn

+ 

¹ 

率は冗長化により

N)./G

となる。従って、切替回路の影響を無視するには).5<え

/G

なお切替回路については 1P Eあたりの故障率をえ sとすると、

ー66‑

とする必要がある。

的と言える。

5.  3.  2 誤り訂正機能の付加の効果

PE内およびPE問で通信されるデータを符号化し、誤り訂正能力を付加する場合の効 果について示す。

図5. 3にこの場合のPE構成と PE間接続について示す。同図に示すように誤り訂正 回路(以下ECCと呼ぶ〉は、通信処理部(以下CPと呼ぶ)と CPUの聞に設置する。

これにより、 CPUが自PE内のメモリを使用する場合だけでなく、 PE間通信において もECCが機能することになり、メモリだけでなく CP部の障害あるし1はインタフェース 線の障害にも対処可能となる。

誤り訂正符号(1ビット誤り訂正を想定する)を適用した計算機全体の信頼度関数R(t)  は、下式で与えられる。

R(t)=  (RPE(t)) _~ = _(R~ (t)

・

Ry (t))  _~ ( 5.  9) 

ここで

R  pd 

t) 

R~ (t)  e ‑l II 

λl  R y (t) 

:PEの信頼度函数

:PEのうちECCにより高信頼化できない 部分の信頼度関数

:同部分の故障率

:ECCにより高信頼化できる部分の信頼度関数

=eλObl+b e‑lo  (b‑Il  l(l‑e‑λo l) 

ス 。 = ん /a

λ2 

a 、b N 

:向上部分の lビット当りの故障率 :向上部分の故障率

;信号ビット長、符号長 :計算機の PE数

上 式 と (

5 .   3 )

式を用いて算出した冗長化による

MTTF

向上度

G

の一例を図

5 . 4 

に示す。同図により、 PE数が多い場合(例えば、 10³ ‑‑‑‑10⁵ )には、 Gは飽和し(え l

+え 2)/λ1に近づくことがわかる。すなわち、この場合には、計算機の

MTTF

はEC Cにより高信頼化できない部分，例えば各種制御回路等データ系以外の部分により決定さ れることになる。

‑68‑

(') 

也

H

4 

在

u^国

ト ト

， 

^0 3 

1 0 2 

~ 1 0 

他PE

へ

r一一一J、一一一、

図5. 3  誤り訂正符号の適用

デ ー タ 幅 =

1 6

ピ ッ ト の と き (a = 

1 6

， b = 

2 2 )  

A1 

J=  : ECCにより高信頼化

A 1 

+ 

^A 2  できない部分の比率

1 0  1 0 2  1 0 3 

P E数 :N

1 0 4 

他PE

へ

〆ー‑‑‑‑'、ーーーーーー、

1 0 5 

図5. 4  誤り訂正符号の適用によるMTTF向上

‑69‑

J=O.Ol 

=一一

J =0. 02 

J=0.03  J =0. 05  J =0. 1  J =0. 2  J=0.3  J=0.5 

1 0 6 

以上のように、誤り訂正符号の適用は

ECC

により高信頼化できない部分が多い場合に は、それのみでは計算機全体のM T T F向上にあまり効果的とはいえない。しかし、 P E 数が多い場合にはP Eの等価的な故障率をえ l程度にできることから、これまで述べてき た他の冗長方式と組み合わせて用いればその効果は大きいと言えよう。さらに、本方法は インタフェース線(リンク)の障害にも対処可能という特徴を有するため、実際の障害が 半導体部品だけでなく、ハンダ接続やコネクタ接続等の各種接続点の不良に起因すること が多いことを考慮すると、極めて実際的な冗長方式であるといえよう。

5 ̲  4  _{ネ ッ} ト ワ ー ク 主 主 主E 7リ言十算事E杉虫色の言会佳斤才去

5 .   2

節で述べたように故障検出においては、稼働率の向上の観点から診断の並列化が 必要となる。これを実現する方法として、

i )各P Eの自己診断 u)隣接P Eによる相互診断

が考えられる。 i)はP Eが故障している場合には、当然、診断結果の正当性は保証され ない。一方、 u) に関しても同様のことがいえるが、試験する P Eを複数にすることによ り結果の正当性を高めることができると考えられる)) 4.  ) ) 5)。しかし、註)は外部端子か らP E内部を試験しなければならないため、試験内容の詳細さは i)より劣る。

そこで、ここではネットワーク型並列プロセッサの並列診断法として、 i )と u)とを 組合せ、診断結果の正当性を高確率で保証でき、かっ、 P E内の詳細部まで試験できる新 たな手法を提案する。本診断法は、被診断PEと直接リンクにより結合された隣接 P Eの 診断結果の多数決により故障を検出する方法であり、以下、

NV C N e i g h b o r   V o t i n g )

診断 法と呼ぶ。本診断法の概念を図 5. 5 (各P Eが 4本のリンクを持つ場合)に示す。

( 1 )  診断手JII員

診断は以下の手順で行う。

i )被診断P Eは自 P E内のテストプログラムを実行する (PEはプログラム走行の機能 を持つことが前提)。

u) テスト結果は全隣接P Eに送出し、その期待値との照合は自 P Eおよび全隣接 P Eで

イ丁つ。

出〉隣接P Eは照合結果を被診断 P Eに返送する。

iv)被診断P Eは照合結果の多数決を採り、自 P Eの良否判断を行う。

本診断法では被診断P Eが故障している場合にはテスト結果が期待値とはならず、隣接 P Eでの照合において故障と診断できる。また、隣接 PEが故障している場合でも、 (隣接 P Eの数)

+ 

1個の P Eのうち過半数の P Eが正常であれば、それらにおいて被診断 P E の故障を検出できることになる。すなわち図 j. Jの場合、 5P Eのうち 2以下の PE故

‑70‑ ^司j

A 円v︐t

る。

障を許容して正当性を高めた診断が可能となる。また、この方法では、 診断 (手順出の照 合処理)を割り込みルーチンで行うことで、全P Eが同時に試験と診断を行うことができ

" 

MN  

ハU

Tl AハT' 

PL V‑

1‑J 

p ' ﹁ 巳

 

V八

戸ト﹄  本診断法は以上述べたように並列診断が可能な他、次のような特徴を持つ。

イ)テスト結果をP E聞のリンクを用いて送出することにより、リンク自身の故障も検出 可能(被診断P Eの故障と等価)。

ロ)各

PE

が

2

以上の

PE

と結合される全てのネットワーク型並列プロセッサに適用可能 (トリー、

2

次元アレイ、ハイパキューブ等)。

(NEIG

珂

EXPECTATION" 

EXPECTATION" 

EXPECTATION" 

￨川

^RATOR

^I 

1 .

  CO~P

^ARA TOR

ト

^{、， ，、}

I 

COMP ARA TOR 

I  ~

^、，

，

、 VOTER 

，

、

I 

FAULT凡 TEST RESUL T" 

(NEIGHBOR PE)  (PE UNDER‑DIAGNOSIS)  (NEIGHBOR PE) 

( 2 )  必要なハードウェア

本診断法では、各P Eがプログラム走行機能を持つことを前提としており、テストプロ グラムの実行およびテスト結果の照合はその機能を利用して行う。従って、本診断法で専 用に必要となるハードウェアは

イ)多数決回路

ロ)照合結果を被診断

PE

に返送するための信号線

のみである。即ち、数 10ゲ ー ト +1本/リンクのハードウェア量である。

従って、これらハードウェアの故障率はP E全体のそれらに比し極めて小さく、その故 障による誤診断はほとんど無視できるといえよう。

(NEIGHBOR PE) 

COMPARATOR長

" M川ハU

Ti

 

Aハ

ri ll

Tl 

pl u  仁﹂

DI V八

F↑

﹄

 

図

5 . 5 

_N V(Neighbor  Voting)診断法

ー

7 2 ‑

^{司 ︐t 司︑υ}

5 ̲  5  ヂド吉言言 ^{多~6 主主} 2 と欠ヨ王アレイ主~CC>フォ一一ノレトトレラ ン ト キ 毒 尾 文 才 去

高並列計算機の高信頼化に関し、まず、保守周期、経済性、稼働率の観点から少ない冗 長度で

MTTF

を向上できる冗長構成およびシステム再構成の自動化とその際の診断の並 列化が重要な課題となることを示した。

次にP E間結合構造に依存しない一般的並列計算機において、 PEを切替単位としてn 重化あるいは n

+ 

1予備を適用した場合、冗長構成を適用しない場合に対して、 P E数を

N

としたとき

MTTF

をQ(N¹/2

)倍程度向上できることを示した。又、両方式の場合の

M TTF

向上度は、それぞれ、

N

1 ‑1 /n ， 

N 

1/2 /  nで近似できることを解析的に示した。

さらに各P E内に誤り訂正機能を付加すると、 P Eの故障率を等価的に削減できるだけで なく、 PE聞のインタフェース線であるリンクの障害にも対処可能となることを示した。

又、 PEの試験結果を複数の隣接P Eで照合させ、その結果の多数決により良否判定を 行う並列診断方法 (NV診断法〉を提案した。

6 ̲ 

_{1  来者言言}

本章では、 2次元アレイ型のネットワークトポロジに適したフォールトトレラント構成 法を提案する。

2次元アレイ型のフォールトトレラント構成については、高信頼化だけでなく複数P E を大型LS 1上に一括集積化する際の欠陥救済の観点からも広く研究されている。例えば、

M .   S a m i

らはいくつかの予備P E列を設け不良PEを隣接P Eで置き換える構成を提案し ているが⁷²⁾ 、基本的には l次元的な k OU t 0 f n 方式であり、不良P Eが連続する 場合にはさらにその隣のP Eで置き換える構成のため、切替えのためのPE聞の結合が複 雑化する欠点がある。又、

A . D .   S 

i 

n g h

は隣接する

4

P E毎に予備P Eを設ける構成を提 案しているが⁷¹ )、この構成は

MTTF

向上効果が高いという利点はあるものの、基本的 に冗長度が高くかっリンクの途中に切替えスイッチを要する等の問題がある。又、横田ら は、 Hobonetと呼ぶ上下方向に隣接する 2P E間にスイッチを設け、これにより不良P E を迂回する構成を提案しているが73 )、行方向を単位とした n

+ 

1予備構成であるにもか かわらず、 P E聞の結合が複雑かつリンクの一部が2つの結合に共用される等の問題があ る。

ここでは、切替えのための P E聞の結合を比較的容易に実現でき (PE外にスイッチも 不要)、かっ少ない冗長度で

MTTF

向上効果が高い、 2次元 n

+ 

1予備と呼ぶ新たな冗 長構成を提案する。この構成は l行 l列の予備PEを設け、 n

+ 

1予備を階層的に適用す

るものである。

以下、 6. 2節で2次元 n

+ 

1予備の構成概念、 6. 3節で同構成を用いた場合の

MT TF

向上効果と切替え回路の影響、

6 . 4

節で同構成を実現するためのP E間結合構成と そのための切替え制御法、、 6. 5節でN V診断法(前章で提案)との組合せによるシス テム自動再構成法およびこれによる無保守化システム実現の可能性について述べる。

ー74‑ ^JU Fh

門t

a

冗長度Jを以下の様に定義すると、

弓手イ庸if誇 疋 文 1 

沙之::::rcn  ート

2  2  6 ̲ 

(予備

PE

数)/ (本来の

PE

数) 一 一

TJ 

PE

を正方格子状に結合した

2

次元アレイ型では、前章の一般的な冗長構成以外にその 構造的特徴を利用した効果的な冗長構成が考えられる。

わ と し て 比 較 的 n J ， 

X 

n 

2 )となり、

(nl+n2+1) / (nl  本構成では、 J =

個、列方向 n2個の

PE

よりなる小

P PE

群を行方向 nl

2次元n

+ 

1予備構成とは、

2重化構成等に比べ充分これを小さくできる。

大きな値を選べば、

n 

+  1

予備を

2

次元的に適用する構成

E

群に分割し、各

PE

群に l行17¹Jの予備を設け、

又、列方向では

PE

単位、行方向では

PE

列単位というように冗長構成が階層的に適用 この構成では同図に示すように、列方向に不

lに本構成の概念図を示す。

である。図

6 .

されるため、高いMTTF向上度が期待できる。

良

PE

がl個以下の場合にはその列を良としてn2十 l個からn2個の

PE

を用い、又、不 良

PE

が2個以上の場合にはその列を不良列とする。同じく、行方向について n1 

+ 

17 Ji 列用いることで

n

1 X 

n 

2の2次元アレイを再構成す から、不良

PE

が

l

個以下の列を nl

る。

n 

t +   1 

ー

7 7 ‑ n 2 + 1  

spare  PEs 

faulty  PE  X :  

good  column 

図 ー 凹

l

巴

l

凹

l

巴 ー

一行一列の予備を設けた冗長構成

ー76‑ good  column 

由 甲 出 回

出

faulty  column  good 

column  good 

column 

図 6.

弓宅;"{J筒

C

こ よ る

M T T F

の

‑

1 

←  

2 と欠ヨ王 n f旬 ー ヒ

3  6 

(1) MTTF向上効果

この冗長構成を適用した計算機の信頼度関数は、切替回路の影響を無視すると、下式で 与えられる。

1 )  ( 6 .  (1 ‑ R₁(t)) )刈

Rdt)"1  (n1+1) 

(R 1 (t)"1 +1 

+ 

R (t) 

一

ここで、

n = 5   n = 1 0   n = 3 0   n = 1 0 0  

n 

n 2 

n = 2   1 0

⁴ 

1  0

³ 

。

日 ?と

ω E ω

﹀O

一 ε

﹂ ロ

R dt)= r (t)" 2"'"1十(n2+1 )r(t)":( 1 ‑r(t)):列の信頼度関数 :小

PE

群数

︑ ー ' ' '

η& 

n 

M=N/  ( n  

1 

即ち、計算機全体はM個の小

PE

群に分割され、その小

PE

群毎に2次元 n

+ 

1予備が適

1  0

² 

用される。

H ‑

ト ト

2

4 )式に代入することによ

1 )式のR(t)を 前 章 の (5 .  ( 6 . 

MTTF向上度Gは、

n 1 

1 0  

n 1.  n 2が比較的小さい領域 (n1. 

2に

G

の計算例を示す。同図より、

り求まる。図 6.

PE

毎に2重化した場合のそれを上回ることがわか

< 

1 0)でのMTTF向上度は、

n 2 

1  0 

5 

1 0

³ 

1  0

² 

2 1 % (2重化の l n1=n2= 10の場合、

この構成の冗長度

J

は、例えば、

るつまた、

1  0

⁶  N 

1  0

⁴ 

Number  of  PEs  /5)となる。即ち、本構成は少ない冗長度で2重化以上のMTTF向上を実現できる効

果的な冗長構成と言える。

図6. 2  _{2次元n+l予備によるMTTFの向上} ( 2 )切替回路の影響

次に本構成における切替回路の影響と最適な切替単位について考察する。切替回路を考 1 )式の左辺と切替回路の信頼度関数Rs

‑79‑ 2より Gは切替単位が小さい程 (Nが大

切替え単位当たり a1/2個の

PE

分の切替回路が必要となり、また計算機全体では

(N/

a) 

2次元アレイでは、切替単位を

a

1/2行

xa 

1/2列の

PE

群

( PE

数は

a)

とした場合、

きいことと等価)高くなる。一方、切替回路の金物量は

PE

間の接続量に比例するため、

=N/a 

1/2個の

PE

分の切替回路が必要となる。従って、

慮した場合、計算機全体の信頼度関数は(

6  . 

の積となる。切替回路を含まない場合には図 6.

ー

7 8 ‑

x  a 

1/2 

E F

ら守系吉

弓ミト

6

筒GC>ナこ bうGC>

P 

壬さ「す去と七刀毛主

F?

乙借リ往日主去 1 

沙之::rcn  ート

4  2  2 )  6 

( 5 .  : P E 1個の切替回路の故障率

= 

exp (‑λsN/a 1/2 

え5

ここで R s (t) 

6. 

4 .  

_{PE問結合法} これを含めた計算機全体の

となり、切替単位aが大きい程R^s (t)は高くなる。従って、

3にMTTF向上度 MTTFを最大にする最適な切替単位が存在することになる。図

6 .

2次元n

+ 

^{1予備では、列方向の}n

+ 

^{1予備においては不良}PEはその下隣の PEによ ん/えが小さい場合(

Gの最大値と、切替単位aの最適値の計算例を示す。同図より、

り代替され、行方向については不良PE7¹J全体が右隣のPE列で代替されねばならない。

後述するようにMIMD形 PEではこの程度)には切替回路の影響は小さく、

<  0 . 0 0

 ，1

前者の条件から斜め方向のPEとの接続が必要となり、又、両者の条件から不良 PEのバ ん/えが大きい場合にはNの増大と共

切替単位も PE単位で良いことがわかる。なお、

イパスが必要となる。斜め方向のPEとの接続を実現するには、基本的には PE当たり 8 にaを大きくし、複数のPE群を切替え単位として二次元n

+ 

1予備を適用するべきと言

ここではパス結合を利用しこれを 6本に削減できる PE間結 本のリンクが必要になるが、

える。

合網(その形状より IX‑NETと呼ぶ)を提案する。又、不良 PEのバイパスについて この場合隣 PEの外部に隣接 PEを迂回する接続線を設けて実現する方法もあるが、

は、

PE内部にパイパ PE間結合が複雑化する。従って、

接する 4方向にこれが必要となり、

ス機能を設ける。

/A 

= 0 . 0 0 0 1   A  •

1 0 ' 

( 凶 牛

) ^図

6 .

4に1X‑NETの PE間結合およびこれによる 2次元n

+ 

1予備構成のための

1 X‑NETでは、縦方向に隣接する PE間 切替え法を示す。同図 (a)に示すように、

= 0 . 0 0 1  

1 0 ³ 

(IJ 

(9 

はl対 lのリンクにより結合され、縦方向、横方向、斜め方向に隣接する 4P Eはパスに このPE間結合において、不良 PEは同図 (b)のように切り離され、

X: fau I ty  PE  より結合される。

= 0 .  0 1  

= 0 .  0 0 1  

= 0 .   1 

= 0 .   1 

= 0 .  0 1  

1 0

⁶  1 0 5 

• •

︐ •

‑ •

•

•

N 

1 0 '  

Number  of  PEs 

1  0

³ 

1  0

² 

1  0 

V

一

_υ

一

o

∞

四C

一工

OH

一主

ωヤOのN

一

_ω

E_H コE

一

a o H C ω ε ω

﹀O﹂QE

一

竹山トト三

c)  Switching  Method  for  Faulty Column  b)  Switching  Method 

for  Faulty PE 

二次元n+l予備のPE問結合網

‑81‑ 4 

a) 

I X ‑ N E T  

図6. 切替回路のMTTFへの影響と最適切替単位

‑80‑ 3 

図 6.

I X‑N E Tの切替え制御では、図 6. 4から分かるように、 2次元アレイの 4方向の

faul ty ∞￨はm 不良 P Eチ^JIは 同 図 (c)のように切り離される。ここで、いずれの場合にも切り離される

P Eにおいてバイノぞス機能は正常であることが前提となる(この前提は、

6 . 4 . 2

で述 べるように切替え制御回路のハードウェア量が極めて少ないこ とから現実的と言える)。 以上の説明から分かる様に、 IX‑NE T  は P E聞の接続構造が単純であり、また、 X 形の部分についても、固定的な 2P E聞の通信に専用的に用いられ競合が生じないため、

アービトレーションが不要という特徴を持つ。即ち、単に 4P Eをパス接続しておくだけ でよい。さらに、結合形状が完全に均一であり、 P E当たりのリンク数も少ないため、 P

E

全体を

LS 1

化する場合にも適している。

6 .   4 . 2 

切替え制御法

インタフェースに対して P Eの6本のリンクのうちのどれを対応させるか、あるいは P E 内でどのリンク聞をバイパスさせるかを決定する必要がある。

この方法としては、 P Eアレイの外部に専用の制御回路を設ける集中制御法もあるが、

制御回路と P Eとの間に個別の信号線が必要になり、高並列計算機には適さない。従って、

ここでは切替え制御回路を全 P Eに分散させ、 P E自身が自律的に切替えを制御できる以 下の方法を提案する。

a)  Propagation of Switching Control  Signals 

的

︑

←

白 し︾

山n

Fc 

，‑ー・・・・・・寸・・・・・ーーーーーー・ーーー‑‑‑‑‑‑‑1

F 

r 

F r 

i) P E間で行方向には不良列の存在を示す信号 (Fr)を、列方向には不良 P Eの存在 を示す信号

(Fc )

を図

6 . 5 

(a)のように伝播させる。ここで、

F r 

， 

F  c

は、例 えば同図 (b)のように作成される。

u) これらの信号と自 P Eの良否 (F^p e) 、自列の良否(F ^c 1m) および P Eの物理的位 置により、図6. 6のように P Eのインタフェースの方向、バイパス等の接続を決定す る。なお、以上の信号は不良の場合をつ"とする。

Fclm  Fc 

b)  Generation Circuit  for Switching Control  Signals 

図

6 . 5

から分かる様に、

F r

は不良 PE7¹J以降(右側の列)、

Fc

は不良 P E以降〈

下側の PE) それぞれ全て 1"となる。即ち、これらの信号は、 P Eアレイにおいて自 P E以前に不良 P E列あるいは不良 P Eが存在する(

o

"の場合には存在しない)こと を示している。又、 F^c 1m は同図 (b)から分かる様に、列方向において2個以上の P E

図

6 . 5 

切替制御信号の伝播と生成回路

ー

8 2 ‑

^‑83‑

~

^{P  1} 

^I 

^{P  2} 

^I 

^{P  3} 

^I 

^{P  4} 

^I 

^{P  5  P  6} 

1  X X X   中 申 串 ^{E 与} 中申

0 1 1 X   工 主 申 申 m =   ^{司 I 申}

0 1 0 X   工 主 申 ^{工 主} 日 ^{自 申}

0 0 1 1   8  ^{工 3} E  8  ^{工 E} ー

0 0 1 0   z z   B  ^申 z z   ^{Z E}   o 

0 0 0 1   8  0 =   o  ^{首 I 申 j 申}

0 0 0 0   z z   ^{自 j 自} ー ^{自 j 申}

一 一 一

が不良の場合に 1"となる。これらの信号を用い図 6. 6の様に接続を制御することに より、不良PEの切離しと予備PEの組み込みが行われる。同図ではPEの6本のリンク がどの方向のインタフェース(上下左右方向をそれぞれN、S、W、Eで表す)として使 用されるか、あるいはどのリンク聞がバイパスされるかを示している。{7jlえば、 P2の位置

(図

6 . 6

の下図参照)のPEで、

F

^c 1m， 

F 

^p et 

F 

^r ， 

F 

^cがそれぞれ

0

，

0

，  ，1 の場合には、 N、S、W、Eの各方向のインタフェースとしては、それぞれ上側、下側、

左上、右上のリンクが用いられる。文、

P 4

の位置のPEで、

F

c 1m， 

F 

^p e， 

F 

r ， 

F 

cが それぞれ0，1， 1， 0 (1でも可〉の場合には、左上のリンクと下側のリンクが接続(

バイパス、図中では矢印で示される)される。

図 6. 7に、以上の手順による切替え例を<1x 4のPEアレイ(予備を除いて)の場合 について示す。この場合、前述の最初の例のPEは同図の4行、 4列自の PEにあたり、

後の例のPEはl行、 57iJ自のPEにあたる。同図から、 2個以上の不良PEを含む列が

F=Fclm / Fpe / Fr  / Fc  X:  Not  exist  NO:  Shut  off 

Faulty  Column 

↓ 

︒

u

nH  

I目 ︑

内b門ヨ・1E門川VA‑ta 

戸MφL

q u 

n n

・lm川m川VA

u u e  

O F巳

O F

﹂

ハ し

門γ

pu

pa

v y v y v y v y  

+L+L+L+L 

HUHUHU

川u

aaaa 

﹁ ﹁

F﹁

﹁﹁

﹁﹁

・・V EV‑

・v'va' 門U門V門U円u︐+lp+t4lF

守﹄

︐a‑

・v sva‑VE‑ nunvnu

門V+LφL+L+L nU2M会

U 3 u

puvFunUFM 

AUAUJU︐o 

n H n H n H n H  

m 

l l e  

pv

門UFvlFM

﹁﹁

﹁﹁

﹁﹁

﹁﹁

Physical Location of  PE  i n PE‑Ar ray 

w ‑ Q ‑ ^E 

Pl

→

^j

口口口口口

^j

←

P4

;口口口口 i 口 ;

P2

→ ; 口口口口口

^j

←

P5

: 口口口口口:

P3

→

^j

口口口口口

^j

^←

^P6

日

X  Faulty  PE 

図6. 6  二次元n+l予備の IX‑NETにおける接続法 図

6 . 7 

_{二次元n+l予備の切り替え例}

ー84‑

‑85‑

1 7¹Jで、他の子JIがl個以下の不良PEの場合には、本来の4

x 

4のPEアレイが再構成で きることが分かる。この切替は、不良P Eを検出し故障フラグに 1"をセット (Fp e  

= 

けすることにより、 P E群内で自律的に行われる。なお、この切替制御に必要な金物は、

図6. 5，図 6. 6を実現する回路およびインタフェースの切替部であり、例えば、イン タフェースを4ビットとすると、 300ゲート程度で実現できる。又、このうちその故障 が計算機全体の故障につながる部分は 100ゲート程度と小さい。

‑86‑

6 ̲  5 

シ ス テ ム 自 重 力 事 計 者 尾 文 字 去

6.  5.  1 自動再構成法

ここでは、 2次元n+1予備において不良PEをl行 l列の予備P Eで置き換え、もと のサイズ (nX n)のPEアレイを自動的に再構成する手順について示す。これは、

5 .

4節のN V診断法による P Eテストにより不良P Eを検出し、前節の切替え制御法により これを切り替えることにより実現される。

図

6 . 8

に、

4

X 

4

のP Eアレイを再構成する場合を例とした自動再構成手順を示す。

この再構成は電源投入時あるし1はPE故障検出時に行い、最悪 4回の PEテストと切替え 操作の繰り返しにより実現される。まず、 N V診断法により予備PE以外の 16個のP E をテストし、不良P Eを検出する(同図(a) )。不良P Eの故障フラグをセットし、こ れを列方向の予備P Eで置き換え、同図 (b)の状態とし、新たに組み込まれたP Eを同 様にテストする。これらが全て正常のとき(列方向において不良PEが l個以下のとき) は再構成はこれで完了する。この例では予備P Eにも不良があり、列方向において不良P

Eが2個以上となるため、列全体を不良とし予備P E列を組み込む必要がある(同図 (c ) )。次に、新たに組み込まれた予備PE7¹Jをテストする。この列の最初の 4PEが全て 正常のときは再構成はこれで完了する。この例では予備P E列にも不良があるため、予備 P E列の最後(アレイの右下)のP Eが組み込まれ、テストされる(同図 (d))。この P Eが正常のときは再構成は成功するが、これも不良の場合は、不良PEが2個以上の列 が2列となり再構成は不能となる。

以上のように、この方法では最悪でも 4回のP Eテストで再構成が実現され、しかもP EテストはN V診断法により対象となる全P Eで同時に実行されるため、再構成に要する 時間は4テストサイクルで済む。即ち、 MTBFに対してMTTRを無視できる程度に短 縮することが可能となる。

6 .   5 .   2 

無保守化システム実現の可能性

P Eとしてマイクロプロセッサ規模 (Cp 

u

を数10¥ ，1‑...;数1001¥ゲート，メモリを数100¥1 数Mバイト程度)を想定すると、故障検出および切替制御に必要な金物量は前節より P

‑87‑

一ー一一ー‑+

a)  Initial  state  b)  State  after  1st  test 

ピ /

ーーーーー‑‑‑+

c)  State  after  2nd  test  d)  State  after  3rd  test 

図

6 . 8 

システム再構成

Eの0.001以下となる。従って、図 6. 3から、例えば n= 1 0、切替回路の故障率As 

= 0 . 0 0 1  

Aを想定すると、 MTTF向上度Gは約 130となり、 PE数N= 1 0 ~の計算機 のMTTFは、 PE故障率え =103fitのとき約1.5年、え =10²fitのとき約 15  年となる。

また、 5. 4節のN V診断法による並列診断および前述のシステム再構成の自動化によ り、 MTTR句 Oにでき、稼働率=r1が達成できる(付録2参照)。

以上より、 2次元 n

+ 

1予備を適用した高並列計算機は高信頼・無保守化システムにで きる可能性があると言える。また、この場合、各部の接続をコネクタ類を用いず固定化で きる等、実装上の利点も期待できることになる。

6 ̲ 

_{6  系吉言言}

2次元アレイ型のネットワークトポロジに適合したフォールトトレラント構成を提案し た。具体的には、

イ)小さい冗長度で2重化以上のMTTF向上度が得られる、 l行 1列の予備PEを設け n 

+ 

1予備を階層的に適用する冗長構成法 C2次元n

+ 

1予備)

ロ)各PEに予備リンクを2組設け各PEが斜め方向のPEとも結合可能とした、 PE間 結合構造が単純かっ切り換え制御も容易な、 2次元

n + 

1予備向きのPE間結合法 C1 

X ‑N E T) 

ハ) P Eと列の良否情報、隣接PE間に伝播させた故障情報を用いた、 PE群内での分散 的かっ自律的な切替制御法

を提案し、これを適用した場合のMTTF向上効果を解析的に明らかにした。

又、 4. 4節のNV診断法の併用により、 PE故障時のシステム再構成の自動化が実現 できることを示した。更に、例えば、 PE数N

= 

1 0 ~の並列計算機 CP E故 障 率 え =1 

0²‑‑‑1  03fit，切替回路の故障率As =O.OOlA)のMTTFを、冗長度約 20%で 約1.5‑‑1 5年に、この間の稼働率をほぼlにでき、高信頼な無保守化システムの実現の 可能性があること明らかにした。

多手?;

7

主主 ノ¥イ'ノ々ニトュ一一フ、、O.Jフ ォ 一 一 ノ レ ト ト レ ラ 本構成法は、予備

PE

と本来の

PE

の聞の接続にクロスパスイッチ等の切替え用ノ¥ードウ エアを不要とし、かつ如何なるサイズのハイパキュープにも適用できるという特徴を有す ン ト コ 構 疋 文 字 去

る。

7 ̲ 

1 

^緒

以下、 7. 2節でこの構成法を導くための諸定義、 7. 3節で、二つのベースとなるフォ ールトトレラントなハイパキュープの構成法と構成例、ならびに複数の

PE

故障を許容で、

きる構成への拡張法、 7. 4節でそれらの任意のサイズのハイパキューフ♂への拡大法につ いて述べ、 7. 5節でこれらを必要となるハードウェア量およびMTTF向上の観点から 評価する。

本章では、ハイパキュープの結合特性に着目した、切替え用ハードウェアを不要とする 新たなフォールトトレラント構成法の提案を行う。

ハイパキュープ(以下キューブとも呼ぶ)については、いわゆる graceful degradati  on" の概念に基づく研究が多い11 6・11710 すなわち、

PE

故障の場合にはキューブのサイ スeを縮小し、もとの数以下の

PE

数で動作を継続する形態であり、この場合には当然本来 のシステム性能以下での動作となる。これを避けるためには、予備

PE

を付加しもとのサ イズのキュープを再構成する必要があるが、これは単純には、

PE

毎に

2

重化するか、あ るいは予備

PE

を全

PE

と結合しておき、いずれの

PE

とも置換え可能としておくことで 実現できる。しかし、前者の場合には冗長度が高く、又、後者の場合には予備

PE

に

PE

数に等しい数のリンクが必要となり、大規模システムでは実現困難となる。

このため、もとのキューブを分割した小さなキュープ(以下サプキューブと呼ぶ)毎に lつの予備

PE

を設け、予備

PE

とサブキューブ内の

PE

とをクロスパスイッチで接続す る構成が提案されている7 5 1 0 しかし、この方法はクロスパスイッチおよびその接続制御 が必要なことは勿論のこと、クロスパスイッチ自体もサブキューブのサイズにより一義的 に定まることとなり、汎用性が無い等の問題がある。

本章で提案するフォールトトレラント構成法は、

PE

番号のハミング距離に着目した

PE

群のグルーピングとグラフの積によるキューブの拡大"を利用したものであり、以下 のアプローチをとる。

イ)全

PE

をその番号の聞のハミング距離に基づき、 すべての

PE

が同一集合内の

2

個 以上の

PE

と結合することがない(集合内の

PE

聞のハミング距離は

3

以上) "ような 複数の集合に分割し、集合内のすべての

PE

と予備

PE

とを集合ごとにパス接続するこ

とにより、ベースとなるフォールトトレラントなキューブを構成する。

ロ)次に、そのベースとなるキュープをグラフの積を利用して拡大し、より大きなフォー ルトトレラントなキュープを j尋る。

‑90‑ ‑91‑

7  2  言者支

E

幸義

( 1 )フォールトトレラントなキューブ

リジッドな結合およびフォールトトレラントの概念について定義する。

〔定義7. 1)  2個のPE間が l対 lに結合されているとき、あるいは3個以上のPE が何らかの機構により共通に結合されているが、その機構はあらかじめ定められた

2

個の

PE問の結合にのみ専用的に用いられるとき、その結合はリジッドであるという。

3個以上のPE聞の結合がパスにより実現される場合、そのパスがリジッドであればそこ での競合は起こらず、アービトレーション機能は一切不要である。

〔定義7. 2)  任意のk個以下の PEが故障しでもそれを除いてn次元のハイパキュー ブ(以下、 n次元キューブ)を再構成可能でき、かっ再構成に用いられる結合がリジッド であるとき、これをk故障に対してフォールトトレラントなn次元キューブ(以下 k ‑

FTn次元キューブ)と呼ぶ。

(2) H D ‑ d集合とその構成法

ここでは， k‑FTn次元キュープの構成に用いる H D ‑ d集合を定義し，さらにその 構成法について述べる。

〔定義7. 3)  以下の式を満たす全PEの集合 Sの部分集合 S⁰， S lt・・・， S ^M‑I を各々 H D  

一

d集合と呼ぶ。

SOUS1U S2 ・・・ U S :.1‑1 

= 

^S 

'SKnsL

=

ゆ

(  0 

~玉 K ，

L 

豆

M‑1 )  

dH(ai.aj)孟d (Val，ajESK) 

ここで a¹， a J はそれぞれPE i.  P E j の番号、 dH (al，aj) はPE iとPE j の 番号聞のハミング距離である。

すなわち. H D ‑ d集合とは、その集合内の各PEの番号間のハミング距離(以下 dH

‑92‑

と略す)が互いにd以上であるPEの集合である。ここでは、その構成法の例として、線 形符号を用いる方法を示す。

線形符号C (n， k)とは、 3. 2節でも述べたように次式を満たす nビット 2元系列 w (符号語と呼ぶ)の集合である。

H  w 

T 

=  0 

(rn 0 

d  2  ) 

_{( 7.  1)} 

ここでHはパリティ検査行列と呼ばれる n‑k行n

7

1Jの行列であり、 Tは転置、 rnod2 は演算が2を法として行われることを示す。 Wのnビット中、 kピットは独立変数(情報

ビットと呼ぶ)、残り n‑kビット(検査ビットと呼ぶ)は(7.  1)式により決定され る。このとき、 Hの列ベクトルの任意のd‑ 1個以下の和 (rn0 d 2 )が非零ならば、 ( 

7.  1)を満たす2^k個のwについて互いの間のd_{H はすべて}d以上となることが知られ ている_II 2)  (最小距離dの線形符号と呼ばれる)。これらwをPE番号aとみなすことに より、 H D ‑ d集合の一つが構成できる。一般には次の補題が成り立つ。

〔補題7. 1)  全てのnビット長PE番号の集合Sを、最小距離dの線形符号C (n，  k)によって展開した剰余類 S0， S 1，・・・， S ~-l は各々 HD-d 集合となる。

( 証 明 ) C (n， k)により展開した Sの剰余類とは，次式で定義される集合 S0， S 1， 

‑・・， S ~-I をいう。

So =C (n， k) 

S 

L 

= 

{a 1 +  a f (L) } 

(V a i E S 0， a f (L) 

$ 

S K.  0壬K <L)  S 0 U S I U •••• U S M‑I 

= 

^S 

このとき、 SK. S L ( K 

< 

L)に同じ PE番号が存在すると仮定すれば、ある ai， a j ( 

E S 0)に対し、 a^I 

+ 

a ( (K)  = a j十 af (L)となるが、

a f (L) = a 1 +  a j + a f (K)  (a i + a j = a "，E S.o) 

ニ am 

+ 

a f (K) E S K 

となって矛盾する。よって、 SK n SL =ゆ である。又、同じ SK 内のPE番号 ao， a Q 

聞の d_Hは、

‑93‑

d H ( a ^p， a Q)  = d H ( a ⁱ 

+ 

a / ^(K)， a ^J 

+ 

a / ^(K) ) 

7 ̲ 

_{3  k  ‑ F  T}  i と欠三五ヰニューーブ、 ι~ ;f蕎尾文字i去

=dH(a" aj)きd (a" ajESo) 

が成立する。以上より S0""'" S ~ー l は HD-d 集合。 ( 証 明 終 )

k‑FTi次元キューブ・は基本的には i次元キューブlこ予備PEを付加し、それらを図

HD‑d集合の具体例としてn=6のHD‑3集合を表7. 1に示す。これは以下のH 行列で定義される線形符号C (6， 3)を用い、補題7. 1に基づいて構成したものであ

7.  1のように結合することにより得られる。従って、予備P Eとi次元キュープ聞の結 合法が主要課題となる。

る。

， ¹¹⁰¹⁰⁰

^寸

H =  I 

0 1  1  0  10 

I 

LI0I001

..J 

各

S K

を構成するための a川町には，符号Cの情報ビットに対応する上位3b i tがす べて

o

"、検査ビットに対応する下位

3 b 

i tが非零で互いに異なるものを用いた。こ れらは各々ほかの集合には含まれない。なぜなら

S

。には情報ビットがすべて

o

"の

P

E

番号は一つしか含まれず、その検査ビットはすべて

o

"だからである。

7.  3.  1 予備PE 1個の l‑FTi次元キューブ

〔構成法 1

a  J

次元キューブに対し、 l個の予備PEを設け、 i次元キュープの各P EをHD‑3集合S1.  S 2

・ ・ ・

S~-I に分割し、各集合毎に集合内のすべての PE をパス結 合 (WiredO R接続〉し予備P Eに結合する(図7. 2)。

〔補題7. 2 

J 

キューブ結合において、すべてのPEは同一のHD‑3集合内の 2個以 上のP Eとの間で結合(リンク〉を持たない。

(証明) Si内の番号a、bのPEが共に、番号CのPEと結合していたとすると、

表

7 . 1 

HD‑3集合の具体例 (n= 6の場合)

S 

。

SI  S 2  S 3  S4  S 5  S ⁶  S 7 

0 0 0   0 0 0   0 0 0   0 0 1   0 0 0   0 1 0   0 0 0   0 1 1  

000 

1 0 0  

000 

1 0 1   。 。 。 _{1 1 0   0 0 0   1 1 1}  

0 0 1   0 1 1   0 0 1   0 1 0   0 0 1   0 0 1   0 0 1   0 0 0  

001 

1 1 1   0 0 1   1 1 0   0 0 1   1 0 1   0 0 1   1 0 0   0 1 0   1 1 0   0 1 0   1 1 1   0 1 0   1 0 0   0 1 0   1 0 1   0 1 0   0 1 0   0 1 0   0 1 1   0 1 0   0 0 0   0 1 0   0 0 1   0 1 1   1 0 1   0 1 1   1 0 0   0 1 1   1 1 1   0 1 1   1 1 0   0 1 1   0 0 1  

011 

0 0 0   0 1 1   0 1 1   0 1 1   0 1 0   1 0 0   1 0 1   1 0 0   1 0 0   1 0 0   1 1 1   1 0 0   1 1 0   1 0 0   0 0 1   1 0 0   0 0 0   1 0 0   0 1 1   1 0 0   0 1 0   1 0 1   1 1 0   1 0 1   1 1 1   1 0 1   1 0 0   1 0 1   1 0 1   1 0 1   0 1 0   1 0 1   0 1 1   1 0 1   。 。 。 _{1 0 1   0 0 1}  

110 

0 1 1   1 1 0   0 1 0   1 1 0   0 0 1   1 1 0   。 。 。 _{1 1 0   1 1 1   1 1 0   1} 1 0   1 1 0   1 0 1   1 1 0   1 0 0   1 1 1   0 0 0   1 1 1   0 0 1   1 1 1   0 1 0   1 1 1   0 1 1   1 1 1   1 0 0   1 1 1   1 0 1   1 1 0   1 1 0   1 1 1   1 1 1  

Connection  Hypercube  for  fault‑

connectlon  tolerance 

n‑dimensional  hypercube 

o 

Original  P 

E  。

^Spa r e P 

^E 

図

7 . 1 

フォールトトレラントなハイパキューブの基本構成

‑ 9 4 ‑

nud Fhd 

 

〆

A 

と他のP Eとの聞のリンクは、予備 P Eと本来の P Eとの聞の結合 ブ結合における

P E 

i 

=2  +dH(b

， c) 

c)  a， 

三

三 d H ( 

b)  d H (a， 

2の関 と他のP Eとの間の結合に関しては補題 7. 

P  E 

i 

この場合、

で置き換えられる。

dH孟3であることから矛盾。

HD‑3集合Si内の各P E間は これは、

となる。

と置き換った予備P Eも同一集合内の 2以上の P Eと結合されるこ

P  E 

ⁱ 

係があるため、

(証明終)

i次元キューブを再構成する際、予備P Eはパス結合された複数の P E とはない。即ち、

よってこのパスはリジッドである。

のうちただ一つの P Eのみとしか結合されない。

l‑FTi次元キューブで 構成法 1aにより得られるネットワークは、

1 

J 

〔定理7. 

ある。 (証明終)

HD‑3集合 3にl‑FT3次元キュープの構成例を示す。 ここで、

図

7. 

〔構成例〕

これらの結合はすべてのP E閣のり 予備P Eは全 P Eと結合されているので、

(証明〉

........，  S 3 は S 

。

ンクを代替できる。従って、パスでの競合を許せばi次元キュープを再構成できることは

111ta

ll

ノ

nH U

司Fム

ーi n U

守E E A

‑

‑ a A

FE‑‑﹄Ell‑也 ︑

3 

B 

~

l‑FT3次元キューブの構成例

‑97‑ H 

図7. 

P  E 

ⁱ 

の代替をする)。キュー

1個の予備PEによる l‑FT 次元キューブ

‑96‑

よって、再構成に用いられる結合(パス)がリジッドであることを示す。

明らか。

が故障し、それを予備P Eと切換えたとする〈予備 P Eが PE i 

M  Su

b s e t   S j  

J/~

B u s  

豆)』レ

^{γ /}

豆 y

。 S p ^{a r e}

^陀

豆 〉 イ

豆 y

宝 〉 イ 宝 〉 ベ

‑ d i m e n s i o n a l   h y p e r c u b e  

0:  O r  i g i n a l

陀

c o n n e c t l o n   H y p e r c u b e  

図

7 . 

2