JPH02294766A - フォールトトレラントシステム及び該システムの構築方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 Ａ．産業上の利用分野 本発明はフォールトトレラントシステムに関するもので
ある。

Ｂ．従来の技術及びその課題 コストの減少及びより高い効率の両方の利益を確保しな
がら非常に大きな計算能力を提供するだめの方法として
並列処理は広く用いられている。

実時間の応答及び並列処理の莫大なデータセットの処理
を利用するタスクには、たとえば次のようなものがある
。天気予測、．マップ作成、空気力学シミュレーション
、化学反応シミュレーション、画像強調、音声認識、航
空交通管制などである。

このようなシステムでは、全て、複数のプロセッサが相
互に接続され、各々が様々な機能を同時に遂行する。そ
のようなシステムを作動させるためには、これらの複数
のプロセッサと、たとえばメモリモジュールの如き他の
装置とをネットワークする必要がある。

そのような相互接続手法においては，接続されたノード
間で高速かつ融通性のある通信（コネクション）を行う
必要がある。ネットワークにノードをたくさん接続すれ
ばするほど、全てのノード間で相互接続を行うことが困
難になってくる。ネットワークにおけるノードの数が増
えるにつれて、１つのノードと他のノードとの直接的な
接続は禁止されるようになってくる。並列処理の場合、
各プロセットと各メモリモジュールとの間で直接的なコ
ネクションを提供することは経済的な側面及び設計選択
の側面の双方により非現実的である。

ネットワーク機構に関する別の面からの要望はフォール
トトレラントであることである。このことにより、ネッ
トワークにおけるいずれかのリンクがダウンした場合に
ネットワークトラヒツク及び通信を継続することを保証
するために動作するバックアップネットワーク又は並列
ネットワークが存在することが要請される。

オメガ、ベースライン（ｂａｓｅ　ｌ　ｉｎｓ）、デル
タ（Ａ＝Ｂ＝２）　、一般化されたキューブ（ｇｅｎｅ
ｒａｌｉｚｅｄｃｕｂｅ）、間接２進Ｎキューブ（ｉｎ
ｄｉｒｅｃｔ　ｂｆｎａｒｙＮ−ｃｕｂｅ）　、シャツ
フル交換（ｓｈｕｆｆｌｅ　ｅｘｃｈａｎｇｅ）及びＳ
Ｗ−Ｂａｎｙａｎ　（　Ｓ　＝　Ｆ　＝　２　）のよう
な多くのネットワークが並列処理ネットワークシステム
において使用されている。これらのネットワークは全て
トボロジー的には等価である。これは、Ｓｉｇｅｌ，Ｉ
Ｉ．Ｊ．，　Ｈｓｕ．　Ｗ．Ｔ及びＪｅｎｇ＋　’によ
る”ＡｎＩｎｔｒｏｄｕｃｔｉｏｎ　ｔｏ　ｔｈｅ　Ｍ
ｕ１ｔｉｓｔａｇｅ　Ｃｕｂｅ　Ｆａｍｉｌｙｏｆ　Ｉ
ｎｔｅｒｏｃｏｎｎｅｃｔｆｏｎ　Ｎｅｔｗｏｒｋｓ，
　”（Ｊｏｕｒｎａｌ　ｏｆＳｕｐｅｒ　ｃｏｍｐｕｔ
ｉｎｇ，第１巻、第１号、１９８７年）に述べられてい
る。

ネットワークに接続された全ての装置への全てのプロセ
ッサによるアクセスを実現するため、ネットワークは交
換ボックス（Ｓ轄ｉｔｃｈｉｎｇ　ｂｏｘ）を使用する
。このような交換ボックスの設計は当業者には知られて
いる。

ところで、並列に動作するネットワークとして同一構成
のものを使用する従来のフォールトトレラントシステム
では，交換ボックスに障害が発生した場合におけるトラ
ヒツク負荷の変動の分配の不均一性の度合が大きいため
にデータ通信の高速性及び効率の点で問題がある。

本発明はこの問題を解決することを目的としている。

Ｃ．課題を解決するための手段 この目的を達成するため、並列に動作する複数のプロセ
ッサを相互接続するために互いに並列に動作する第１及
び第２のマルチステージネットワークを有する本発明の
フォールトトレラントシステムは、上記第１のマルチス
テージネットワークが等価的オメガ構成で配置されかつ
上記第２のマルチステージネットワークが等価的逆オメ
ガ構成で配置されることを特徴としている。

また、並列に動作する複数のプロセッサを相互接続する
ために互いに並列に動作する第１及び第２のマルチステ
ージネットワークを有するフォールトトレラントシステ
ムを提供する本発明の方法は、（ａ）　　上記第１のマ
ルチステージネットワークを等価的オメガ構成に変換す
るステップと、（ｂ）上記第２のマルチステージネット
ワークを等価的逆オメガ構成に変換するステップと、（
ｃ）　　上記等価的オメガ構成及び上記等価的逆オメガ
構成を並列に動作させるステップと、 を有することを特徴としている。

本発明の方法及びシステムはネットワークが等価的オメ
ガネットワークとして構成できるような任意の並列ネッ
トワークに適用することができる。

ネットワークはいずれも等価的オメガ構成において機能
する又は配列されるオメガに変換することができる。こ
れは本発明の並列ネットワークの一方の逆オメガ構成に
ついてもあてはまる。

したがって本発明の方法において、第１及び第２のマル
チステージネットワークは、たとえば、オメガ（ｏｍｅ
ｇａ）ネットワーク、ベースライン（ｂａｓｅｌｉｎｓ
）ネットワーク、デルタ（ａ＝ｂ＝２）ネットワーク、
一般化されたキューブ （ｇｅｎｅｒａｌｉｚｅｄ　ｃｕｂｅ）ネットワーク、
間接２進（ｉｎｄｉｒｅｃｔ　ｂｊｎａｒｙ）ネットワ
ーク、シャツフル交換（ｓｈｕｆｆｌｅ　ｅｘｃｈａｎ
ｇｅ）ネットワーク、ＳＳＷ−ｂａｎｙａｎ（Ｓ＝Ｓ＝
２）ネットワークのいずれであってもよい。

以下、本発明の作用を実施例とともに説明する。

Ｄ．実施例 第１図には，共有メモリを有する並列フォールトトレラ
ントシステムｌＯが示されている。システム１０は並列
に動作する交換網４及び６を含む。

これらの交換網は複数のプロセッサ２もしくは複数のメ
モリモジュール８又はその双方の間の相互接続交換網と
して機能する。このシステムにおいては、どのプロセッ
サも他のプロセッサからのアクセスとは無関係に任意の
メモリモジュールをアクセスすることができる。たとえ
ば、このネットワークシステムの１つの実施例において
、２つのネットワークのうちの一方が複合可能なメッセ
−ジの処理を任命され、他方が複合不可能なメッセージ
の処理を任命されているとする。しかしながら、一方の
ネットワークに障害が発生した場合に他方のネットワー
クが双方のネットワークのトラヒツクを処理できるよう
、いずれのネットワークも両方のタイプのメッセージを
処理することができる。これは、本質的に、当該技術分
野で知られている並列構成のフォールトトレラントネッ
トワークの１つのタイプの動作である。本発明は一殻的
にはＮがシャツフルないしは組替え（ｓｈｕｆｆｌｅ）
すべき入力の数であるようなｌｏｇｚＮ個のステージを
有する並列ネットワークに適用される。

第２図はネットワークを１つだけ有する（したがってフ
オーノレトトレラントではない）システム２０を示す図
である。交換網２２にブレークダウン又は障害が発生し
た場合、システム２０は動作することができないゆとい
うのはプロセッサとメモリモジュールとの間のデータフ
ローが維持されなからである。ブレークダウンには様々
な形式のものがある。たとえば、欠陥のある交換ボック
ス、切断されたコネクション、不良コネクションなどが
ある。

第３図はネットワーク３０ａ及び３０ｂを有するシステ
ム３０を示す図である。システム３０はネットワーク経
路（又はリンク）が完全な組替え構成（ｐｅｒｆｅｃｔ
　ｓｈｕｆｆｌｅ　ｃｏｎｆｉｇｕｒａｔｉｏｎ）で分
配されるような８つのブロセウサ及び８つのメモリモジ
ュー゜ルを有するオメガネットワークの形式でシステム
１０がいかにして組立てられるかを示す特定の例である
。この３ステージ、８プロセッサ、８メモリモジュール
のシステム３０は１つの構成例にすぎないことに留意さ
れたい。本発明のシステム及び方法は任意のｌｏｇ．Ｎ
ステージネットワークについて｛幼く。

オメガネットワークにおいては，交換ボックス６４ない
し７０及び対応する交換ボックス６４″ないし７０′で
ステージ１が構成され、交換ボックス７２ないし７日及
び対応する交換ボックス７２゛ないし７８′でステージ
２が構成され、交換ボックス８０ないし８６及び対応す
る交換ボツクス８０゛ないし８６゛でステージ３が構成
される。

各交換ボックスは２つの人力及び２つの出力を有する。

負荷分配の計算において、いずれかの入力で受取られた
メッセージはいずれかの出力に均等な機会で経路指定し
うるちのお仮定した。

システム３０においては，プロセッサ３２ないし４６は
第１のオメガネットワーク３０ａを介してメモリモジュ
ール４８ないし６２に接続される。

第３図のネットワーク３０ｂにおいては、第２のオメガ
ネットワークがフォールトトレラントを保証するためネ
ットワーク３０ａに並列に接続されている。交換ボック
ス６４ないし８６及び６４゛ないし８６”によって各プ
ロセッサが各メモリモジュールへのアクセス権を有する
ことが保証される。参照文字Ｌは各自のデータラインな
らびに入力ボート（Ａ，Ｃ）及び出力ボート（Ｂ，Ｄ）
を介して各交換ボックスに入る又は交換ボックスから出
ていく単位時間当りのトラヒツク量の等しい負荷を表わ
している。ネットワーク３０ａ及び３０ｂの双方で、こ
れらの負荷は障害又はブレークダウン状態が存在しない
場合には均等に分配されるということがわかる。この例
では、プロセッサの要求は全てのメモリモジュールにわ
たって均一に分配されるものと仮定した。

これに対し、第４図はブレークダウンが生じた場合にお
ける並列ネットワーク３０ａ及び３０ｂの動作を示す。

第４図のネットワーク３０ａ及び３０ｂでは、交換ボッ
クス６６の“゜Ｘ′”はそれが故障していることを表わ
している。この場合、データが交換ボックス６６を介し
て伝送されることはなく、プロセッサ３４及び４２はメ
モリモジュール４８ないし６２とは通信することができ
ない。

このシステムは第４図における同一のオメガネットワー
ク３０ｂと並列に走行しているので、交換ボックス６６
を介するトラヒツクは交換ボックス６６゛を介して再割
当てされる。したがって、交換ボックス６６゛を介して
伝送される負荷は実質的に倍になる。これは第４図の交
換ボックス６６′の人力及び出力のところの゛２Ｌ゛゜
で示されている。かくして、ネットワーク３０ｂはトラ
ヒックのフローに関してもはや均等な分配を有していな
い。

第４図のネットワーク３０ｂにおいて、“Ｌ゜゜や“″
２Ｌ′゜などの負荷指数で示されるようにトラヒックの
分配は均一ではない。ネットワーク３０ｂのステージｌ
では、交換ボックス６６”から出るトラヒツクは両方の
出力からそれぞれ２Ｌてある。ステージ】の他の全ての
交換ボックスはＬの出力負荷を有する。ステージ２では
、交換ボックス７６′及び７８゛は各出力ボートを介し
て１．５Ｌの出力負荷を有する。この１．５という係数
は交換ボックス７２′及び７４″からの出力よりもさら
に２分の１だけ多いことを意味する。ネットワーク３０
ｂのステージ３の出力負荷は均一である。

ネットワークにおいては各ステージの負荷はできるだけ
均一であることが好ましいので、以上に示したような均
一でない負荷は望ましくない。負荷の均一性によって、
トラヒツクがどの交換ボックスにも分配されれば、より
高速でより効率的なデータ伝送が保証される。

第５図はネットワーク３０ａのステージ２の交換ボック
ス７６においてブレークダウンが生じた場合におけるシ
ステム３０の動作を説明する図である。交換ボックス７
６がブレークダウン又は故障すると、その交換ボックス
を介して関連するプロセッサ又はメモリモジュールに伝
送すべきデータの経路はもはや存在しない。これにより
、ネットワーク３０ａのステージ１における交換ボック
ス６６及び７０を介するトラヒック負荷が減少する。交
換ボックス６６及び７０への入力は交換ボックス６６が
動作不能なのでそれぞれ１．ＯＬだけ減少する。

ネットワーク３０ａ及び３０ｂの間の合計の負荷の差異
はλＯＬである。第５図のネットワーク３０ａの負荷は
交換ボックス６６において合計Ｉ．Ｏ　Ｌ　（０．５　
Ｌ＋０．５　Ｌ）だけ減少するので、ネットワーク３０
ｂを介するトラヒツク負荷は対応する量だけ増加しなけ
ればならない。これは交換ボックス６６゛への人力にお
いて示されている。ここで、これらの入力は各人カボー
１−Ａ及びＣに対してそれぞれ１．５Ｌである。これは
合計１．ＯＬ（各ポートにつき０．５Ｌ）の負荷の増加
であり、ネットワーク３０ａを介する負荷の減少に等し
い。

同じことは交換ボックス７０及び７０′にもあてはまる
。

第５図に示すようにネットワーク３０ａの交換ボックス
７６における障害による負荷の増加があるため、ネット
ワーク３０ｂはもはやその通信１・ラヒツクについて均
一な分配を持たない。これはネットワーク３０ｂの３つ
のステージの各々における出力についての不均一性でわ
かる。特に第３ステージでは、交換ボックス８０゛及び
８２′の各出力が１．５Ｌてあり、交換ボックス８４゛
及び８６′の各出力がＬとなっている。

次に第６図を参照する。第６図では、システム３０はネ
ットワーク３０ａのステージ３の交換ボックス８２にお
いてブレークダウン又は障害が存在する。これまでの２
つの障害の例のように、全てのプロセッサ及び全てのメ
モリモジュールの間の通信を維持することを保証するた
め、トラヒツクはネットワーク３０ｂを介して再経路指
定されなければならない。ネットワーク３０ｂの交換ボ
ックス８２′における不均一な量のトラヒック負荷によ
ってトラヒツクフローはもはや均一でなくなる。

本発明に従って、第７図においてシステム３Ｉは所与の
どの交換ボックスにもトラヒックを分配して、ネットワ
ークの全体にわたってより均一なトラヒツクフローパタ
ーンを確立する。システム３１は、いずれかの交換ボッ
クス又はリンクにブレークダウン又は障害が生じた場合
に、フォールトトレラントを提供するため．並列に動作
する。

しかしながら、システム３０とシステム３Ｉとの違いは
、第７図においてネットワーク３ｌｂがネットワーク３
１ａと同じではないことである。ネットワーク３ｌｂは
逆（逆転された）オメガネットワークとして定義される
。この新しいデザインは第１のネットワークにおける交
換ボックスにブレークダウンが存在する場合にも生じる
増加したトラヒツク負荷を第２のネットワークの複数の
交換ボックスに分配する。これを行うにあたり、トラヒ
ックフローが第２のネットワーク全体にわたってより均
一に分配され、したがってシステム全体のデータ伝送の
効率と正確さの両方が改善される。

第７図に示すシステム３１は第４図に示すシステム３０
ａと対比することができる。第７図のネットワーク３１
ａでは、第４図のネットワーク３０ａと同様に、ステー
ジｌの交換ボックス６６に障害が存在する。しかしなが
ら、第７図のネットワーク３ｌｂに示す第２のネットワ
ークに振り向けるべき増加したトラヒック負荷は第４図
のネットワーク３０ｂの場合に比べてステージＩ及びス
テージ２を介して不均一性はより小さくなっている。第
７図のこの逆オメガネットワーク３ｌｂは増加したトラ
ヒツク負荷を交換ボックス６４′及び６８゛で受諾する
。したがって、第２ステージではトラヒックフローはそ
の４つの全ての交換ボックス７２゜ないし７８”にわた
って既により均一に分配されている。ネットワーク３ｌ
ｂの第３ステージでは、出力トラヒツクフローだけでな
く入力トラヒックフローも均一かつ同一である。

これは第４図に示すような２つの同一のオメガネットワ
ークが並列に使用された場合とは異なる。

既に説明したように、第４図のネットワーク３０ｂのト
ラヒツクフローはそのステージ全体にわたる均一性はな
く、第３ステージで均一に近づいているにすぎない。ネ
ットワークのデザイン及びアーキテクチャの最終目標は
、正確でしかも効率的なデータ伝送及び通信を保証する
ためにできるだけ均一なトラヒツクフローを提供するこ
とにある。

第８図に示すシステム３０は第５図に示すシステム３０
と同様に、ステージ２の交換ボックス７６において障害
を有する。再び第８図のネットワーク３ｌｂにおいて逆
オメガデザインを用いることによって、第５図のネット
ワーク３０ｂで説明したトラヒツクの不均一性の問題が
ほとんど解決されている。第２のステージの交換ボック
スの障害が発生した場合は、トラヒツク負荷の分配は第
１のステージの交換ボックスの障害の場合よりもずっと
破壊的である。この様子は第５図に示されている。

第８図のネットワーク３ｌｂにおいて逆オメガを使用す
ることによって、トラヒック負荷は第１ステージの出力
から第３ステージの入力まで均一である。第３ステージ
の出力は第５図のネットワーク３０ｂの場合よりも十分
に均一である。

システム３０を構成するネットワークの入力及び出力に
おける合計の負荷は均一でなければならないということ
に再び留意されたい。このことは、合計８Ｌの入力及び
８Ｌの出力が存在することを意味する。したがって１つ
のネッ１・ワークにおいて１つの交換ボックスの障害が
存在しかつトラヒツクを第２のネットワークを介して再
経路指定しなければならない場合は、システムの合計の
負荷は影響を受けない。第８図において、ネットワーク
３１ａの交換ボックス７６の障害によって交換ボックス
６６では負荷係数が１だけ減少し、交換ボックス７０で
も負荷係数が１だけ減少することがわかる。しかしなが
ら、システムの合計の入力及び出力の負荷はトラヒック
の再経路指定が存在するかどうかにかかわらず依然とし
て同じである。

同じことはネットワークの出力についてもあてはまる。

どの交換ボックスにも障害が存在しない場合は各ネット
ワークの合計の出力は８Ｌである。

障害の際には、合計の出力は１つのネットワーク当り８
Ｌの出力に等しいのであるが、その分配が異なるのであ
る。これは第８図のネットワーク３１ａにおける交換ボ
ックス８０出力のＩＬ及び交換ボックス８２の出力のＩ
Ｌの減少にみられる。

この合計２Ｌの減少は第８図のネットワーク３１３０ｂ
の出力に分配される。この分配は第５図の場合に比べて
より均一である。何故なら第５図では交換ボックス８０
’及び交換ボックス８２゜の出力ポートＢ及びＤだけが
増加されるのに対し、第８図では交換ボックス８０”な
いし８６゛にわたってその出力が０．５Ｌだけ増加され
ているからである。

第９図に示すシステム３１は第６図のシステム３０の状
況と同様に、ステージ３の交換ボックス８２に障害が存
在する。しかしながら第９図のネットワーク３ｌｂは逆
オメガネットワーク構成を用いて、この障害状況につい
てのトラヒックフローを分配している。第９図のネット
ワーク３１ａでは、交換ボックス８２の障害によってメ
モリモジュール５２及び５４の通信が不能となっている
ことがわかる。交換ボックス８２を介する伝送を必要と
するトラヒックはネットワーク３ｌｂに示される逆オメ
ガネットワークに再経路指定される。

第９図のネットワーク３ｌｂにおける１・ラヒックフ口
一の分配は第６図のネットワーク３０ａと同じオメガネ
ットワークが用いられている第６図のネットワーク３０
ｂにおけるトラヒツクの分配に比してより均一であるこ
とが容易にわかる。完全に均一というわけではないけれ
ども（各交換ボックスの入力及び出力の負荷が全て同じ
というわけではないので）、これはより望ましいデザイ
ンである。

第６図のネットワーク３０ａにおいて交換ボックス８２
゛の出力負荷はボートＢ及びＤからの各２Ｌてあるのに
対し、第９図のネットワーク３ｌｂにおいてはこの２倍
の負荷（２Ｌ）は２つの交換ボックス８４゛及び８６゛
に分配され、しかも各交換ボックスの一方の出力ポート
だけからである。さらに、ネットワーク全体にわたる負
荷の分配は、たとえばステージ２おいてみられるように
、より均一に行われている。第２ステージの交換ボック
スの全ての入力はｌ、２５Ｌであり、かつその全ての出
力は交換ボックス７２゛ないし７８゛　ともＬ及びＩ．
５Ｌで同じである。

この分配は完全に均一というわけではないけれども現行
のネットワークシステムにおいて広く行われているよう
な二重の同一ネットワークオペレーションを単に使用す
るだけの場合に比べてより均一な分配を得ることができ
る。交換ボックスに障害が発生した場合には、並列して
動作する第２のネットワークに渡すべき増加したトラヒ
ツク負荷があるために、真に均一な分配を実現すること
はできない。それでも、トラヒツク負荷の分配の均一性
の度合をより高めることによって効率及び通信の正確さ
をより良好にすることは可能である。

以上の図面で説明した例は本発明に基づくオメガネット
ワーク及び逆オメガネットワークを用いる並列ネットワ
ークアーキテクチャを示すものである。オメガネットワ
ークアーキテクチャを使用したのは、交換ボックスに障
害が存在する場合に発生する問題と並列ネットワークア
ーキテクチャに対して本発明により達成される改善との
両方を説明するためである。ここで説明したネットワー
クは全て８プロセッサ、８メモリモジュールのネットワ
ークである。これは説明の簡単のために選択したにすぎ
ない。

ベースライン（ｂａｓｅｌｉｎｅ）、デルタ（ａ＝ｂ＝
２）、一ＩＣ化されたキューブ（ｇｅｎｅｒａｌｔｚｅ
ｄ　ｃｕｂｅ）、間接２進（ｉｎｄｉｒｅｃｔ　ｂｉｎ
ａｒｙ）　、フリツブ（ｆｌｉｐ）、シャツフル交１ｊ
ｊｊ（ｓｈｕｆｆｌｅ　ｅｘｃｈａｎｇｅ）、ＳＳＷ−
Ｂａｎｙａｎ（Ｓ＝Ｓ＝２）のような他のネットワーク
は前掲の文献に示されているようにオメガネットワーク
とトボロジー的には等価である（等価的オメガネットワ
ーク）。これらのネットワークの間のネツトワーク再構
成手法は当業者にはよく知られている。したがって上述
の逆オメガネットワークと等価な構成で別のネットワー
クを動作させることができる。この場合、本実施例と同
じ結果が他のネットワークデザインにおいても得られる
。

ネットワークはいずれもオメガ／逆オメガデザインと置
換することができる。すなわち、ネットワークのうちの
一方は使用されている他方の逆オメガ構成として再設計
することができる。これにより、オメガ以外のネットワ
ークを用いる並列ネットワーク機構のオペレーションが
提供される。

この場合、本発明に基づく逆オメガデザインの分配上の
効果も維持される。

逆オメガデザインを達成するためには．オメガデザイン
の完全な組替え分配経路（ｐｅｒｆｅｃｔｓｈｕｆｆｌ
ｅ　ｄｉｓｔｒｉｂｕｔｉｏｎ　ｐａｔｈ）を逆にする
ことが必要である。オメガデザインにおけるネットワー
ク接続の分配は次のように表わすことができる。

＝２ｉ＋１−Ｎ（）　　≦ｉ≦Ｎ−１ ここで、Ｎはシャツフルないし組替え（ｓｈａｆｆｌｅ
）すべき入力の数を表わす。

第１０図はＮ個の入力を有する例示的なネットワークに
関する完全なシャツフルの結果を示す図である．これは
第３図ないし第９図におけるオメガネットワークと整合
するものである。図に示すように、最初の半分の入力（
この例では４つ）は交換ボックスの上位の入力ポート（
第３図ないし第９図におけるボー｝Ａ）に接続され、下
位半分の人力は交換ボックスの下位の入力ポート（第３
図ないし第９図におけるポートＢ）に接続される。

これでオメガネットワークの完全なシャツフルが構成さ
れる。逆オメガネットワークを実現するには、この完全
なシャツフルを逆にすることが必要である。これは次の
ように表わすことができる。

ｊ 逆シャツフル（ｊ）＝（−）ｊ＝偶数 たとえば、Ｎ＝＝８の場合、逆シャッフル（ｒｅｖｅｒ
ｓｅ　ｓｈｕｆｆｌｅ）は第１１図のようになる。完全
なシャッフルは上述の式で表わされるように反対の方向
で行われる。

逆オメガネットワークを構成することによって、同一の
オメガネットワークを並列に走行させる場合に比べてよ
り多くの交換ボックスに増加した負荷を分配することが
できるようになる。

Ｅ．発明の効果 以上説明したように本発明によれば、従来の並列ネット
ワークによるフォールトトレラントシステムに比べて、
交換ボックスに障害が発生した場合におけるトラヒツク
負荷の変動をより均一に分配することが可能となる。

【図面の簡単な説明】

第１図は共有メモリを有する並列フォールトトレラント
システムを示す図、第２図は単一の交換網を示す図、第
３図は３ステージネットワークで構成された並列ネット
ワークシステムならびに各ネットワークを介して接続さ
れた８つのプロセッサ及び８つのメモリモジュールを示
す図、第４図ないし第６図はそれぞれネットワーク３０
ａの第１ないし第３ステージにおける１つの交換ボック
スにブレークダウンが発生した場合の並列ネットワーク
システムの様子を示す図、第７図ないし第９回は第４図
ないし第６図にそれぞれ本発明を適用した実施例の様子
を示す図、第１０図は８人力及び８出力を有する例示的
なネットワークについての完全なシャッフルの様子を示
す図、第１１図は８人力及び８出力を有する例示的なネ
ットワークについての逆シャツフルの様子を示す図であ
る。 出願人　　インターナショナル・ビジネス・マシーンズ
・コーポレーション 代理人　　弁理士　　頓　　宮　　孝　　一（外１名） 弧３リフｔ−ルトｋレラントシステム Ｆ工６．２ ＦＩＧ，１０ シャツフｌレ ＦＩＧ，１１ （ｊ〉 迦シャ冫フＩレ （ｎ

Claims (2)

【特許請求の範囲】
1. （１）並列に動作する複数のプロセッサを相互接続する
   ために互いに並列に動作する第１及び第２のマルチステ
   ージネットワークを有するフオールトトレラントシステ
   ムであつて、 上記第１のマルチステージネットワークが等価的オメガ
   構成で配置されかつ上記第２のマルチステージネットワ
   ークが等価的逆オメガ構成で配置されることを特徴とす
   るフオールトトレラントシステム。
2. （２）並列に動作する複数のプロセッサを相互接続する
   ために互いに並列に動作する第１及び第２のマルチステ
   ージネットワークを有するフオールトトレラントシステ
   ムを提供する方法であつて、（ａ）上記第１のマルチス
   テージネットワークを等価的オメガ構成に変換するステ
   ップと、 （ｂ）上記第２のマルチステージネットワークを等価的
   逆オメガ構成に変換するステップと、（ｃ）上記等価的
   オメガ構成及び上記等価的逆オメガが構成を並列に動作
   させるステップと、を有することを特徴とするフオール
   トトレラントシステムを提供する方法。