JPH05130101A - メツシユアーキテクチヤにおける故障許容のための方法と装置 - Google Patents

メツシユアーキテクチヤにおける故障許容のための方法と装置

Info

Publication number
JPH05130101A
JPH05130101A JP4099996A JP9999692A JPH05130101A JP H05130101 A JPH05130101 A JP H05130101A JP 4099996 A JP4099996 A JP 4099996A JP 9999692 A JP9999692 A JP 9999692A JP H05130101 A JPH05130101 A JP H05130101A
Authority
JP
Japan
Prior art keywords
mesh
node
nodes
fault
faulty
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
JP4099996A
Other languages
English (en)
Other versions
JP2620457B2 (ja
Inventor
Jehoshua Bruck
ジエホシユア、ブルツク
Robert E Cypher
ロバート、イー、サイフアー
Ching-Thien Ho
チン‐テイエン、ホ
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
International Business Machines Corp
Original Assignee
International Business Machines Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by International Business Machines Corp filed Critical International Business Machines Corp
Publication of JPH05130101A publication Critical patent/JPH05130101A/ja
Application granted granted Critical
Publication of JP2620457B2 publication Critical patent/JP2620457B2/ja
Anticipated expiration legal-status Critical
Expired - Lifetime legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G06F11/07—Responding to the occurrence of a fault, e.g. fault tolerance
    • G06F11/16—Error detection or correction of the data by redundancy in hardware
    • G06F11/20—Error detection or correction of the data by redundancy in hardware using active fault-masking, e.g. by switching out faulty elements or by switching in spare elements
    • G06F11/202—Error detection or correction of the data by redundancy in hardware using active fault-masking, e.g. by switching out faulty elements or by switching in spare elements where processing functionality is redundant
    • G06F11/2051—Error detection or correction of the data by redundancy in hardware using active fault-masking, e.g. by switching out faulty elements or by switching in spare elements where processing functionality is redundant in regular structures
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G06F11/07—Responding to the occurrence of a fault, e.g. fault tolerance
    • G06F11/16—Error detection or correction of the data by redundancy in hardware
    • G06F11/20—Error detection or correction of the data by redundancy in hardware using active fault-masking, e.g. by switching out faulty elements or by switching in spare elements
    • G06F11/202—Error detection or correction of the data by redundancy in hardware using active fault-masking, e.g. by switching out faulty elements or by switching in spare elements where processing functionality is redundant
    • G06F11/2041—Error detection or correction of the data by redundancy in hardware using active fault-masking, e.g. by switching out faulty elements or by switching in spare elements where processing functionality is redundant with more than one idle spare processing component

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Quality & Reliability (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)
  • Hardware Redundancy (AREA)

Abstract

(57)【要約】 （修正有） 【目的】 ｄ次元メッシュ・アーキテクチャにおける故
障を許容する方法と装置を得る。 【構成】 アーキテクチャはｋ個までの故障の存在下で
運用可能な目標メッシュとして、スイッチを使用せずに
再構成できる。Ｎ＝ｎ1 ×ｎ2 ×…ｎd 個のノードを有
するｄ次元メッシュアーキテクチャＭを与えられると５
０１、故障許容メッシュに正確にＮ＋ｋ個のノードを有
するサーキュラント・グラフ５０２〜５０４により表現
可能である５０５。このグラフは、１組のｋ個以下の故
障ノードを与えられると、予め定めたノード再命名処理
の実行後、残りのグラフがｄ≧２，ｎd ≧３である限り
目標メッシュに対応するグラフをサブグラフとして含む
ことを保証される。同時に、構築された故障許容メッシ
ュを与えられた時に、ｋ個までのネットワーク構成部品
の存在下で健全な目標メッシュを有効に位置づける。

Description

【発明の詳細な説明】
【０００１】
【産業上の利用分野】本発明は一般的にはｄ次元メッシ
ュアーキテクチャにおける故障を許容する方法と装置に
関する。さらに詳しく言えば、本発明は、（１）事前に
選定した数までの故障を支援し、なおアーキテクチャに
接続された「健全な」メッシュをすなわち容易に識別で
き、またアーキテクチャにより支持されるシステムの性
能低下を受けずに運用できる包含メッシュを含んでいる
と保証され得るメッシュアーキテクチャ、および（２）
故障したネットワーク構成要素の存在下で健全なメッシ
ュを有効に探し出す手法に関する。
【０００２】さらに特定の用語で言えば、本発明の一面
では、Ｎ＝ｎ1 ×ｎ2 ×…×ｎd 個のノードを有するｄ
次元メッシュアーキテクチャＭが与えられると、故障許
容メッシュＭｋは正確にＮ＋ｋ個のノードを有するサー
キュラント・グラフにより表わすことが出来る。ｋ個以
下の故障ノードの組を与えられると、事前に選定したノ
ードの再命名処理の実行後に、ｄ≧２，ｎd ≧３である
限りは、目標メッシュＭに対応するグラフを残りのグラ
フがサブグラフとして含むことが保証されるという特性
を、Ｍｋのグラフ表示は有している。
【０００３】本発明の別の一面では、ｋ個までの故障の
組を与えられて、Ｍｋの中で健全なメッシュＭを発見す
る方法は、（ここでＭｋはＮ＝（ｎ1 ×ｎ2 ×…×
ｎd ）＋ｋ個のノードを有し、ＭはＮ個のノードを有す
る、但しｄ≧２，ｎd ≧３）、（ａ）Ｍｋ中のいずれの
非故障ノードを目標メッシュＭのノードＯの候補と考え
るべきかを定めるステップ、（ｂ）候補非故障ノード中
のいずれが目標メッシュのノードＯであるべきかを定め
るステップ、ならびに（ｃ）識別の組がメッシュＭの行
優先順序づけを表わすように、ノードＯから出発して各
非故障ノードに識別子を割り当てるステップ、とからな
る。
【０００４】
【従来の技術】「メッシュ」は並列コンピュータと要素
配列（例えば、並列メモリ配列）を設計する際、またボ
ードあるいはチップに計算モジュールを接続するための
等に用いられる最も重要かつよく知られた並列アーキテ
クチャの一つである。
【０００５】とりわけ、２次元および３次元メッシュト
ポロジの並列コンピュータが多数現存し、あるいは開発
中である。例として、Goodyear Aerospace製作の２次元
メッシュコンピュータ（「ＭＰＰ」コンピュータ）、
「ＭＰ−１」（ＭＡＳＰＡＲが販売）、「ＶＩＣＴＯ
Ｒ」（ＩＢＭ）、「ＤＥＬＴＡ」（Ｉｎｔｅｌ）があ
る。ＭＩＴで開発中の「Ｊ−Ｍａｃｈｉｎｅ」は３次元
メッシュアーキテクチャの一例である。並列処理を可能
にするシステム、要素配列を含むシステム等の設計での
最も重大な問題点の一つは、故障時のシステム性能であ
る。例えば、並列コンピュータでは、事前に決められた
ある数の故障が存在した場合、同一あるいはほぼ同一の
機能と性能を有するマシンが好まれる。
【０００６】Wafer Scale Integration （ＷＳＩ）配列
は故障許容設計のどこが重要であるかの他の列を提供す
る。ウェーハ上の配列中、構成要素の一つが故障してい
るというだけで全ウェーハを廃却しなくてもよいという
ことは明らかに有利である。ＷＳＩは性能向上の技術で
あるが、主として歩溜りの問題の故に市場ではまだ重大
な衝撃を与えなかった。従って、ＷＳＩ等に用いるよう
なｄ次元メッシュアーキテクチャにおける故障を処理す
る有効な技法（経費の点で）を開発することは実用上非
常に重要である。
【０００７】従来技術の特許や文献は多いが、いずれも
各種応用に対する故障許容ネットワークをいかに作り使
用するかを教えることに向けられている。教えのすべて
にメッシュアーキテクチャの使用を含んでいる設ではな
い。多くの教えは特定型式の故障部品（例えばメモリ部
品やプロセッサ、しかし両方ではない）以外には有効で
ない。さらに別の教えでは、多数の予備部品および／ま
たはスイッチ、余分の通信リンク等を必要とし、これが
ネットワークのコスト増および性能低下の傾向を生じた
り、あるいはネットワーク構造がアーキテクチャに含ま
れる特定部品の故障をマスクすることが不可能である等
の場合には、全然作動しないことになる。
【０００８】例えば、Ｃｈｏａｔｅ等への米国特許４，
０４７，１６３、Ｃｈｏａｔｅへの米国特許４，０５
１，３５４、Ｈｅｎｒｙへの米国特許４，７９１，６０
３は故障許容手法を述べているが、これはメモリ素子の
みに有効で、故障許容相互接続ネットワークに拡張した
り、包含したりはできない。
【０００９】Ｍｏｒｔｏｎへの米国特許４，７２２，０
８４は、共用バスに結合された並列線形配列の使用によ
り故障許容を達成するＶＬＳＩ回路との使用に関する配
列構成機器を述べている。別の「ブス」志向の故障許容
計画はＣｏｒｌｉｅｕへの米国特許４，８９１，８１０
に教えがある。ここではノードがブスに結合されている
再構成可能な計算素子を述べている。一般に、ブス志向
の故障許容アーキテクチャはシステム性能に重大な影響
を及ぼすことがあり、特に、支援されるシステムがブス
回線争奪への可能性およびブス管理コストに敏感な場合
はとりわけそうである。
【００１０】上記に示すように、ネットワークの故障許
容特性を向上させるための従来技術での取り上げ方の多
くにはスイッチの追加を含んでいる。一般に、これらシ
ステムは重大な処理遅れを生ずる可能性を有する。かか
るシステムの例は国際特許出願Ｎｏ．ＷＯ ８９／０７
２９８およびヨーロッパ特許ＥＰ−３９８９７１に教示
されており、スイッチを追加する故障許容ネットワーク
が述べられている。メッセージはこれらの可能な多数の
スイッチを介して送られ、これが望ましくない「減速
（スローダウン）」率を導入することがある。
【００１１】目的を達成するために交換接続にたよる故
障許容ネットワークの別の例が、Ｄａｖｉｓ等への米国
特許４，９２２，４０８に教示されている。ここでは、
故障許容通信を実行するのに、六角形配列を利用する多
重プロセッサ通信システムが述べられている。このシス
テムは、可能な多数の中間ノードを介して送られるメッ
セージを有し、このノードは、再度重大な処理遅れを生
ずる可能性を有する。
【００１２】再び、上記で示すように、故障許容アーキ
テクチャを作るために予備ノードを追加する構想もまた
知られている。しかし、公知の手法のいずれも次の点を
考慮していない。即ち（１）追加される予備ノードの数
を最小にすることによりネットワークコストを最小にす
ること、（２）多次元メッシュにおける（予め決められ
た数ｋまでの）複数の故障を支援できること、（３）ノ
ードを介しての通信が不可能になるような全ノード故障
の場合でさえも故障許容を提供すること、（４）（特定
の故障条件下で動作しつづけなければならない基本ネッ
トワークの程度と比較し）作られつつある故障許容ネッ
トワークの次数を増加しないよう同時に保証すること、
である。）現在の技術水準の他の例が以下の文献に説明
されているが、そのいずれも上記基準を満足していな
い。
【００１３】Ｈａｒｐｅｒ等の米国特許４，９０７，２
３２およびＧｏｒｉｎ等の英国特許ＧＢ２２３１９８５
は並列アーキテクチャにおける悪質（Byzantine ）故障
を許容する手法を教示している。しかし、ｋ個の故障を
支援するのに、少くとも３ｋ＋１個の予備ノードが必要
である。
【００１４】Ｗａｒｅの米国特許４，３０２，８１９は
故障許容モノリシック乗算器を述べている。これは許容
される故障数以上の数の予備品を必要とし、また故障が
発見された時に全列の構成要素を廃棄する。このシステ
ムは予備ノード要求の点でコストがかかる。
【００１５】Ｒａｍａｃｈｅｒ等の米国特許４，９５
１，２２０は１６の次数を有し、かつせいぜい２個の最
悪ケース故障を許容できる故障許容ＶＬＳＩシステムを
述べている。この文献で、特に他次数、限定数の許容故
障の面で教えられる故障許容技法は、多次元メッシュ適
用には適していない。ＷａｒｅやＨａｒｐｅｒ等と同
様、Ｒａｍａｃｈｅｒ等のシステムは、必要なノードの
数が許容される故障の数を越えているので予備ノードの
面でコストがかかる。
【００１６】ＭｃＣａｎｎｙ等の米国特許４，８３３，
６３５は、故障許容の２次元メッシュを含有するビット
スライス型ディジタルプロセッサを教示している。しか
し、故障許容は１次元メッシュを形成するサブシステム
に拡張するだけで、従って実際の適用は制限される。
【００１７】ヨーロッパ特許出願１９０，８１３は故障
許容配列を構成するのに用いるための処理セルについて
述べている。セルは許容故障の数以上の予備を必要と
し、約１０個を有し、また最悪分布の場合ではただ１個
の故障のみを許容できるにすぎない。この明細書に教示
されている処理セルの進め方は予備ノードおよびその数
の要求の点で明らかに貴用がかかる。
【００１８】Ｇｒｉｎｂｅｒｇ等の米国特許４，５０
７，７２６はノード内部の故障許容を提供する装置を教
示している。Ｙｕｎｇの米国特許４，９７０，７２４お
よび国際特許出願ＷＯ ９０／０９６３５は故障許容を
達成するためにある程度まで故障ノードを通る経路を必
要とする故障許容ネットワークを教示している。しか
し、これらの教示のいずれも全ノード故障が生じる立場
では故障許容を提供しない。
【００１９】最近の文献、「メッシュ中の故障回復のた
めのダイアゴナル交換計画」（研究発表説明書Ｎｏ．３
０９、１９９０年１月発行、英国Kenneth Mason Public
ations出版）は最新技術の例を更に示している。ここで
は、並列プロセッサに対する故障回復計画が発表されて
いる。しかしこの計画は直角２次元メッシュのみに有効
であり、最悪分布の場合はせいぜい２個の故障を許容で
きるのみである。
【００２０】
【発明が解決しようとする課題】上記の文献および以下
に引用するその他の文献に照らして、現在の技術水準を
要約すると、メッシュ・アーキテクチャにおいて故障を
許容する基本的方法は２つある。
【００２１】第１の方法はアーキテクチャの健全な部分
を有するメッシュを模擬することにより、故障の影響を
機能的に隠すことである。このアプローチの期待は、適
当な減速率で同一の機能性が得られることである。この
方法はＫａｋｌａｍａｎｉｓ等により、表題「故障アレ
イプロセッサによる計算に対する漸近線的タイトバウン
ド」（コンピュータ科学基金に関する第３１回米国電気
電子学会議事録、PP．２８５〜２９６、１９９０年１０
月発行）の論文中で教示されている。
【００２２】Ｋａｋｌａｍａｎｉｓ等が教示する方法は
理論上は完全であるが、性能上の減速が実用上はそれを
魅力のないものにしている。さらに、Ｋａｋｌａｍａｎ
ｉｓ等の教示は、上記の他の引用文献のあるものと同じ
く、並行マシンにおけるように、１個の構成部品が他の
数個の構成部品を模擬できる時にのみ有効である。ノー
ドがメモリ素子のような、複数構成部品を模擬できない
構成部品から成立しているなら、本文献により教示され
ている方法は望ましい故障許容を提供できなくなる。
【００２３】前記文献の若干の典型となっており、メッ
シュアーキテクチャでの故障を許容する進め型として知
られる第２の方法は、アーキテクチャに予備のプロセッ
サおよび余分のリンクまたはスイッチを追加することで
ある。この進め方の構想は、健全ノードを有する全メッ
シュ構造を維持しつづける一方で、ある接続を無視する
か、あるいはスイッチを設けるかのいずれかにより、故
障を分離するものである。この進め方の側がＫｕｎｇ等
による論文、表題「単一トラックスイッチを用いる故障
許容アレイプロセッサ」（コンピュータに関する米国電
気電子学会会報、Ｃ−３８巻、第４号、PP．５０１〜５
１４、１９８年４月発行）に述べられている。
【００２４】メッシュアキテクチャ内で故障許容を得る
ためのこの第２の既知の進め方はいくつかの面で問題が
ある。例えば、もしスイッチ機構を用いるなら、その機
構自体が故障のないものでなければならない。さらに、
スイッチ、余分のリンク、あるいは予備プロセッサの追
加は、ネットワークコストを上昇させ、従って可能な限
り最も経済的なやり方で行わなければならない。さらに
その上、これら余分の構成部品はアーキテクチャの速度
を減速させる傾向があり、これによりネットワーク性能
を劣化させる。
【００２５】従って、メッシュ・アーキテクチャの故障
許容を達成し、かつ先行技術の故障許容機構で用いられ
るスイッチや余分のリンクの追加を廃除するような方法
と機器を提供することが望まれる。
【００２６】さらに、ネットワークの重大な性能劣化を
生ぜず、またコスト増加なしにメッシュ・アーキテクチ
ャの故障許容を達成できることが望ましい。さらに詳し
くは、構成体のコストを抑えるためには、構成、使用さ
れる故障許容ネットワークの次数（論理出力数）を最小
に保つことが望ましい。
【００２７】さらになお、それぞれの構成部品が、シス
テムの重大な性能劣化を蒙ることなしには、外の構成部
品の役を務めたり、あるいは模擬したりが出来ないよう
なメッシュアーキテクチャにおいて、故障に耐えること
が望ましい。
【００２８】さらにその上、故障許容メッシュを構成す
るのに用いる予備構成部品の数を最小に保つことが望ま
しい。詳しく言えば、許容さるべき故障の数より多い数
の予備構成部品を追加しなくてすむことが望ましい。
【００２９】以下に示すように、上に述べた望ましい特
性のすべてを有する故障許容メッシュアーキテクチャ
が、本発明の一面に従い、次のようなグラフとしてメッ
シュ・アーキテクチャを取り扱うことにより実現でき
る。このグラフでは、グラフのノードは同一構成部品
（プロセッサ、メモリ素子等）を表わし、グラフのエッ
ジは例えば物理リンク、ラジオ通信リンク等のノード間
のリンクを表わしている。
【００３０】各種の異なる故障許容アーキテクチャを開
発するために、グラフモデルを利用する先行技術が存在
していることに注目すべきである。しかし、メッシュ・
アーキテクチャに適用されるような技術は知られていな
い。
【００３１】詳しく言えば、Ｈａｙｅｓは、論文「故障
許容計算システムに対するグラフモデル」（コンピュー
タに関する米国電気電子学会会報、Ｃ−２５巻、第９
号、PP．８７５〜８８４、１９７６年９月発行）中で、
周期、直線配列、ツリーの目標グラフで故障許容グラフ
の使用を教示している。Ｗｏｎｇの論文、「最小Ｋ−ハ
ミルトングラフII」（The Journal ofGraph Theory ，
第８巻、PP．１５５〜１６５，１９８４）およびＰａｏ
ｌｉ等の論文、「最小Ｋ−ハミルトングラフII」（The
Journal of Graph Theory ，第１０巻，PP．７９−９
５、１９８６）は共に周期にのみ関する。
【００３２】Ｄｕｔｔ等によるより最近の刊行物、さら
に詳しくは、論文「ｋ個の故障許容ツリーアーキテクチ
ャの設計および再構成について」（コンピュータに関す
る米国電気電子学会会報、Ｃ−２９巻、第９号、PP．８
３６〜８４０、１９８０）、および論文「故障許容コン
ピュータに関する第１９回国際シンポジウムの議事録、
PP．４９６〜５０３、１９８９年６月）は、それぞれツ
リーとハイパーキャーブからなる目標グラフに関する。
【００３３】上に示したように、上記文献はいずれも、
一般に目標メッシュのような他のメッシュを含む故障許
容メッシュ・アーキテクチャに対するモデルとしてグラ
フの使用を教示していないし、また以下詳細に述べるよ
うな、故障許容メッシュを構築、利用するための特別の
手法も教示されていない。
【００３４】従って、故障許容メッシュ・アーキテクチ
ャを定義、構成、使用するための有効な方法よび装置を
提供することが本発明の１つの目的である。（以下一般
に参照するメッシュ・アーキテクチャはすべて、ｄ次元
メッシュ・アーキテクチャと考えることを意味する。こ
こでｄは任意に選べる整数である。）予め定めた数の故
障を支援でき、なお減速を受けずに作動できる健全なメ
ッシュ接続アーキテクチャを含むことをそれぞれ保証さ
れる故障許容メッシュ・アーキテクチャを提供すること
が本発明のもう一つの目的である。
【００３５】さらに、故障の存在の下で、スイッチを使
用せずに、容易に再構成できる故障許容メッシュ・アー
キテクチャを提供すること、すなわち、故障ネットワー
ク中の健全メッシュを有効に探し出す手法を提供するこ
とが、本発明の一目的である。
【００３６】その上さらに、ｋ個までのノード故障を許
容するために正確にｋ個の予備ノードを追加することに
より、一方では同時にノード当りのリンクの数（メッシ
ュの次数）を最少に保つことにより、故障許容メッシュ
・アーキテクチャのコストを最小にすることが本発明の
一目的である。詳しく言えば、ただ１個の予備構成部品
の追加を要し、かつメッシュの最大次数を増加させない
単一ノード故障を許容するための方法と機器を提供する
のが本発明の目的の１つである。
【００３７】さらになお、並列コンピュータ、他の並列
アーキテクチャ、基板上の素子配列、ＷＳＩ配列、メモ
リ素子等での使用に対し普及できる故障許容メッシュア
ーキテクチャの構築、使用のための方法および機器を提
供するのが本発明の一目的である。
【００３８】本発明によれば、メッシュ・アーキテクチ
ャはあるグラフ中のノードは同一構成部品（プロセッ
サ、メモリ素子等）を表わし、グラフのエッジはノード
間の通信リンクを表わすようなグラフと見做される。
【００３９】本発明のこの見方に従って、「目標メッシ
ュ」Ｍを先づ選定する。ＭはＮ＝ｎ1 ×ｎ2 ×…×ｎd
個のノードを有するｄ次元メッシュ（ここでｄ≧２，ｎ
ｄ≧３）であってよい。続いて、Ｎ＋ｋ個のノードを有
する故障許容メッシュＭｋをサーキュラントグラフモデ
ルを用いて定義、構築する。このグラフは正確にＮ＋ｋ
個のノードを有するものとする。Ｍｋのグラフ表示はｋ
個以下の故障ノードの組が与えられると、予め定められ
たノード再命名処理実行後、残りのグラフはサブグラフ
として含むことを保証され、そのグラフはｄ≧２，ｎｄ
≧３である限り目標メッシュに対応するという性質を有
する。ｎｉとｎｄとは目標グラフの変更なしに変換可能
であるから、ｎｄ≧３の要求は、少なくとも１個のｎｉ
≧３の要求と等価であることに注目すべきである。
【００４０】ｋ個までの故障を支援できる故障許容メッ
シュを得るためには正確にｋ個の予備ノードが追加され
ることに注目すべきである。故障許容メッシュを構築す
るためのこの進め方は、目標メッシュにより支援される
よう設計されたいかなるプロセス、システム等も故障の
分布とは関係なくｋ個以下のノード故障の存在の下で遅
速を生ぜず作動することを保証する。
【００４１】本発明の教示に従って構築される故障許容
メッシュはその組み立てが最小次数（ノード当りのエッ
ジの数）および最小予備構成部品で故障許容グラフを構
築することになるので、最小コストで組み立てることが
できる。
【００４２】さらに以下に詳細に説明するように、与え
られた故障のあるエッジを附随するノードは故障ノード
として取扱えるので、本発明の教えはエッジ故障の許容
（ノード故障と同様）に拡張することも注目すべきであ
る。
【００４３】発明の他の一面によれば、故障許容ネット
ワーク（メッシュ）Ｍｋはｄ次元目的メッシュＭが与え
られると任意に構築できる。ここでＭはＮ＝ｎ1 ×ｎ2
×…×ｎd 個のノードを有し（ｄ≧２，ｎｄ≧３）、ま
たＭｋはＮ＋ｋ個のノードを有し、ｋ個までの故障を許
容できる。本発明の教示に従って構築されるＭｋは、ｋ
個までの故障の発生の際与えられたｄ次元メッシュを形
成するために、スイッチを使用せずにＭｋ中のノードの
いかなるＮも再構成できるという性質を有している。
【００４４】更に詳しくは、本発明のこの分野は、Ｎ＝
ｎ1 ×ｎ2 ×…×ｎd 個の同一ノード（ｄ≧２，ｎｄ≧
３）を有するｄ次元メッシュＭを含む故障許容メッシュ
Ｍｋに関係する。ここでＭｋはｋ個までの故障を支援で
き、かつメッシュＭを形成するのにスイッチの使用なし
に再構成できる。メッシュは（ａ）Ｎ＋ｋ個のノード、
ここで追加ｋ個のノードは、メッシュＭにおけるのと同
じタイプのものであり、サーキュラントグラフで配列す
る。（ｂ）上記サーキュラントグラフに対する複数のエ
ッジはここで、ｋが奇数のときは、次のオフセットの組
の結合により定義される。
【００４５】 ｛１＋ｊ 但し ０≦ｊ≦（ｋ−１）／２｝； ｛ｎ1 ＋ｊ 但し ０≦ｊ≦（ｋ−１）／２｝； ｛（ｎ1 ×ｎ2 ）＋ｊ 但し ０≦ｊ≦（ｋ−１）／
２｝；から ｛（ｎ1 ×ｎ2 ×…×ｎd-1 ）＋ｊ 但し ０≦ｊ≦
（ｋ−１）／２｝；まで またｋが偶数のときは、エッジは次のオフセットの組の
結合により定義される。
【００４６】 ｛１＋ｊ 但し ０≦ｊ≦ｋ／２｝； ｛ｎ1 ＋ｊ 但し ０≦ｊ≦ｋ／２｝； ｛（ｎ1 ×ｎ2 ）＋ｊ 但し ０≦ｊ≦ｋ／２｝；から ｛（ｎ1 ×ｎ2 ×…×ｎd-1 ）＋ｊ 但し ０≦ｊ≦ｋ
／２｝；まで 本発明の更に別の面は、ｋ個までの故障の存在下で、故
障許容メッシュＭｋに健全メッシュを探し出し、作動可
能な目標メッシュＭを得るためにＭｋを再構成する方法
に向けられている。ここで、本発明に従って、（１）
ｄ，ｎ1 ，ｎ2 ，…，ｎd ，ｋの値；（２）サーキュラ
ント・グラフ・モデルで表現した故障許容メッシュＭｋ
の構造、および（３）Ｍｋ中のｋ個までの故障の位置が
与えられると、Ｍを得るためにＭｋ中のノードを「再ラ
ベル」する「再命名」処理が用いられる。本発明の実施
例の一つによれば、新ラベル付けは、健全メッシュを生
ずる非故障ノードの行優先順序付けに対応している。
【００４７】更に詳しくは、ｋ個までの故障の組が与え
られると、Ｍｋ中の健全メッシュＭを見出す方法は（こ
こでＭｋはＮ＝（ｎ1 ×ｎ2 ×…×ｎd ）＋ｋ個のノー
ドを有し、ｄ≧２，ｎｄ≧３，またＭはＮ個のノードを
有する）は次のステップから成る。即ち（ａ）Ｍｋ中の
どの非故障ノードが非故障メッシュＭ中のノード０の候
補と考えるべきかを決定するステップ、（ｂ）候補非故
障ノード中のいずれが目標メッシュ中のノード０である
べきかを決定するステップ、および（ｃ）ノード０で始
まる各非故障ノードに識別子を割り当てるステップであ
る。ここで識別子の組はメッシュＭの行優先順を表わ
す。
【００４８】ここで説明する教示に従って構築される故
障許容メッシュは、予め定めた数までの故障の存在下
で、減速を生ぜずに作動可能な、完全メッシュを含むこ
とを保証されるという保証が、本発明の特徴である。故
障許容メッシュは最小コストで構築でき（次元および予
備構成部品に関し）、また並列コンピュータ、ＷＳＩ配
列、メモリ素子配列等に広い適用範囲を有する。
【００４９】
【実施例】図−１に４列４行を有する２次元メッシュ
（１６ノード）の例を示す。ノードは、ノード１００〜
１１５とラベル付きで示されている。
【００５０】図−２は４個の予備ノード１２０〜１２３
の追加、および図−１に示すメッシュに予備ノードを結
合させるための連結リンク（点線で示すエッジ）を示し
ている。共に結合されると、図−２に示す２０個のノー
ドはある場合には故障を許容でき、またここで述べる発
明を利用することにより解決される若干の問題を例示す
るメッシュとして役立つ。
【００５１】例えば、ノード１０５（図−２の列２に示
す）が故障すると、故障許容を達成するための従来技術
の手法の一つは、図−２の列１，３，４，５が図１Ａの
元の列１，２，３，４の代りをするように、図−２に示
す列を再命名することであった。
【００５２】この案が作動する前提は、図−２メッシュ
から除去される行を経由して、図−２の行１、行３間に
通信が持続されるということであり、故障ノード１０５
を通る通信を含んでいる。この前提は必ずしも正しくは
ないので、図−２メッシュは真の故障許容ではない場合
がある。更にこの簡単な例で故障ノードを含む列を交換
するコストが、単一故障の許容を要求するだけの適用に
おいて、４個の予備ノード（１２０〜１２３）を必要と
する。
【００５３】図示していないものは、スイッチ、追加エ
ッジ等の導入により更に複雑になったメッシュ・アーキ
テクチャの故障許容を達成するための他の従来技術の計
画であって、これらの導入は単純なメッシュでさえも動
作するのにコストを増大させまた性能を劣化することが
ある。
【００５４】対照的に、本発明に従い、与えられたメッ
シュ・アーキテクチャが、グラフ中のノードはプロセッ
サ／構成部品に対応し、エッジはプロセッサ／構成部品
間のリンクであるグラフとして表わされるならば、故障
ノードは予備ノードの追加により扱うことが出来、最小
個数の予備ノードのみを追加すればよい。従って、ｋ個
のノード故障を許容するならば、故障許容メッシュを得
るために目標メッシュにはｋ個のみ（かつ正確に）の予
備品を追加することが必要になる。本発明を実施する
際、後で具体的に説明するが、ｋ個のノード故障の組が
与えられると、健全ノードはすべて健全メッシュとして
構成することが出来る。
【００５５】より形式的に言えば、ｄ次元メッシュＭは
Ｎ＝ｎ1 ×ｎ2 ×…×ｎd 個のノードを有するグラフと
見做すことができる。ここで各ｎｉは第ｉ次元の長さを
規定する。各ノードは形式（Ｘ1 ，Ｘ2 ，…，Ｘd ）の
特有ベクトルでラベル付けされる。ここで１≦ｉ≦ｄの
すべてのｉに対し、０≦Ｘｉ≦Ｎｉである。各ノード
（Ｘ1 ，Ｘ2 ，…，Ｘd ）は形式（Ｘ1 …Ｘi-1 ，Ｘ
i±1 ，Ｘi+1 …Ｘd ）の高さ２ｄ個のノードに連結さ
れる。
【００５６】Ｎ個のノードを有するｄ次元メッシュＭが
与えられると、Ｎ＋ｋ個のノードを有するメッシュＭｋ
は、もしＮ個のノードを有するＮｋのグラフ表示の各サ
ブグラフがサブグラフとしてＭを含むならば、Ｋ−ＦＴ
ｄ次元メッシュと称する。すなわち、グラフＭｋはｋ
個の故障を許容でき、メッシュＭの健全なコピーを含む
ことがなお保証されている。
【００５７】本発明は２つの分離した部分を有する。第
１部はｄ≧２，ｎｄ≧３のｄ次元メッシュＭに対するｋ
−ＦＴ ｄ次元メッシュＭｋの構築のための処理であ
る。第２部はｋ個のノード故障を受けた後に、Ｍｋ中に
存在する良性メッシュの発見のための有効な処理であ
る。この処理は今後は、「再命名」処理として参照する
ことにする。
【００５８】上記の本発明の分離された「部分」は、一
緒に（順番に）あるいは別々に実行できることは、当業
者により、理解されるであろう。例えば、ここでの教示
に従って構築された故障許容メッシュを与えられ、再命
名処理のみを実行することが可能である。実際にノード
故障を関ししたり、健全メッシュを探し出すためにここ
でのべた新規な方法を実行したり当をせずに、ここで説
明する教示を利用する故障許容メッシュを簡単に構築す
ることも可能である。いずれにしても、以後説明される
故障許容メッシュ構築方法と健全メッシュ探査手法のい
ずれか又は両方の実施を容易化する方法および装置を、
本発明は包含することを意図している。
【００５９】概観するに、本発明の構築部分は目標メッ
シュＭをグラフと見做し、故障許容グラフを構築（定
義）し、そこから故障許容メッシュＭｋを表わすことを
考えている。再命名処理は故障の存在下で故障許容メッ
シュの健全ノードに新しい論理ラベルを割り当てること
を考えている。
【００６０】本発明の詳述記述を始める前に、いくつか
の概念を定義しておく要がある。第１に、ｄ次元メッシ
ュは、もし（次元である順序を仮定すると）ノードがメ
ッシュ中のその位置に従って、辞典編集的順序でラベル
付けされるならば、行優先順でラベル付けされると言え
る。例えば、２次元メッシュでは、ノードの位置はその
行と列番号で与えられる。すなわち、ノード（ｉ1 ｊ）
は行ｉ1 列ｊにある。行優先ラベル付けはノード（０，
０）（ここでは「ノード０」として参照する）に始ま
り、辞典編集的に（０，１），（０，２），（０，３，
…，（１，０），（１，１）等と進む。図１Ａに示すよ
うなメッシュが与えられると、行優先順はノード１００
を０とラベル付けし、ノード１０１を１とラベル付けす
る等と進行する。
【００６１】本発明の理解にとって本質的なことは、サ
ーキュラントグラフとして知られるグラフ分類に精通す
ることである。かかるグラフは１組のジャンプあるいは
オフセットを用いてエッジが定義されるＮ個のノードを
有する。定義により、もしｍ個のオフセットの組が｛Ｓ
ｊ，但し１≦ｊ≦ｍ｝ならば、その時は各ノード（例え
ばノードｉ）は、ノードｉ＋Ｓi ，ｉ−Ｓi ，ｉ＋
Ｓ2 ，ｉ−Ｓ2 ，…，ｉ＋Ｓm ，ｉ−Ｓm （ｍｏｄＮ）
に連結される。
【００６２】故障許容グラフ（および対応する故障許容
メッシュ）を構築する際、１組のオフセットを決定する
方法は、ｋが奇数か偶数かによって決まる。このことは
後にさらに詳しく説明する。
【００６３】サーキュラノト・グラフの一例を図−３に
示す。図示のサーキュラント・グラフは２００〜２１５
のラベル付けした１６個のノードを有している。これら
ノードは、例えば図−１に示すメッシュアーキテクチャ
のノードに対応する。当業者は、図−１に示すメッシュ
に比し、図−３に示すサーキュラント・グラフでは、少
数の追加エッジが示されていることを認識するであろ
う。例えば、ノード２００（図−１のノード１００に対
応）は、ノード１００に対する２個のエッジに対し、４
個のエッジを有する。図−１に示されるメッシュは４×
４ ２次元メッシュであるから、Ｎ＝１６であり、ｍ個
のオフセットの組は、後で具体的に説明する様に、
｛１，４｝である。
【００６４】図−３に示すように、図−１に図示したメ
ッシュに対応するサーキュラント・グラフは、（上に示
したように、グラフは少数の追加エッジを含んでいる
が）前記定義に従って、隣接ノードに連結されるノード
を有し（すなわち、通信リング／エッジは１のオフセッ
トを有する）、また各ノードは４のオフセットを有する
ノードにも連結されている。従って、例えば図−３のノ
ード２００はエッジ２５０，２５１を経由して、それぞ
れ隣接ノード２１５，２０１に連結される。同様に、ノ
ード２００はエッジ２５２，２５３を経由し、それぞれ
ノード２１２，２０４に連結される。ノード２０１はエ
ッジ２５１，２５４を経由し、それぞれ隣接ノード２０
０，２０２に連結される。ノード２０１はエッジ２５
５，２５６を経由し、それぞれノード２１３，２０５に
も連結される等が示されている。
【００６５】モジュロＮセンスでは（ここで説明してい
る例ではモジュロ１６）、図−３の各ノードは両方向
（サーキュラント・グラフの周り）のノード±１および
±４に連結されている。
【００６６】図−３に示すサーキュラント・グラフは説
明用のみに示したものである。実際には、前に示したよ
うに、図−１に示すメッシュの「境界」に現われるノー
ド（ノード１００のような）は図−３に示すすべてのエ
ッジを必要としない。従って、再びノード１００を例に
用いるなら、メッシュが適切に機能するためには、２個
の相互連結リンク（エッジ）のみが必要である。一方、
ノード１０５のような「内部」ノードは４個のリンク
（メッシュの最大次数）を必要とする。
【００６７】本発明を理解する上で注目すべく重要なこ
とは、図−３に図示した様式のサーキュラント・グラフ
が、与えられたメッシュおよび支援さるべき故障の最大
個数（ｋ）に、数で対応する追加予備ノードの組から構
築され、ｋ個の故障許容である等価メッシュを組み立て
るモデルとして役立つことがある点である。
【００６８】サーキュラント・グラフは当業者にはよく
知られており、Ｅｌｓｐａｓ等による論文、「サーキュ
ラント近接マトリックス」（組み合わせ理論学会誌、第
９号、ｐｐ．２９７〜３０７，１９７０年）で詳細に記
述されている。Ｅｌｓｐａｓ等の論文は、ここで参考文
献に含める。
【００６９】以下の事項の基礎を築いた上で、故障許容
グラフ、従ってそれに対応する故障許容メッシュを構築
する方法の詳細を最初に一般的応用感覚で述べ、続いて
単一故障を支援するのに望ましいｎ×ｎ２次元メッシュ
の特別事例の具体的実例を述べる。
【００７０】本発明によれば、もしＭがＮ＝ｎ1 ×ｎ2
×…×ｎd 個（ｄ≧２，ｎｄ≧３）のノードを有するｄ
−次元メッシュであり、Ｍｋが対応するｋ−ＦＴメッシ
ュであると定義される時は、Ｍｋは０からＮ＋ｋ−１ま
での番号を付したＮ＋ｋ個のノードからなる。ここでＭ
ｋはｋが奇数か偶数かのいずれであるかの関数としてエ
ッジが定義されているサーキュラント・グラフで表わす
ことが出来る（すなわち、エッジの定義には２つの場合
がある）。
【００７１】事例１ではｋは奇数である。この場合では
各ノードは高々ｄ（ｋ＋１）次数を有する。エッジは次
のオフセットの組の組み合わせで定義される。
【００７２】 ｛１＋ｊ 但し ０≦ｊ≦（ｋ−１）／２｝； ｛ｎ1 ＋ｊ 但し ０≦ｊ≦（ｋ−１）／２｝； ｛（ｎ1 ×ｎ2 ）＋ｊ 但し ０≦ｊ≦（ｋ−１）／
２｝；から ｛（ｎ1 ×ｎ2 ×…×ｎd-1 ）＋ｊ 但し ０≦ｊ≦
（ｋ−１）／２｝；まで 事例２ではｋは奇数である。この場合には各ノードはｄ
（ｋ＋２）次数を有す。エッジは次のオフセットの組の
組み合わせで定義される。
【００７３】 ｛１＋ｊ 但し ０≦ｊ≦ｋ／２｝； ｛ｎ1 ＋ｊ 但し ０≦ｊ≦ｋ／２｝； ｛（ｎ1 ×ｎ2 ）＋ｊ 但し ０≦ｊ≦ｋ／２｝；から ｛（ｎ1 ×ｎ2 ×…×ｎd-1 ）＋ｊ 但し ０≦ｊ≦ｋ
／２｝；まで 上記のサーキュラント・グラフに沿って作られたメッシ
ュ・アーキテクチャＭｋは、ｋ個の故障許容であり、従
ってｋ個までの故障の存在下で、その分布に関係なくメ
ッシュＭを含むことが保証される。
【００７４】実用上の意義のある故障許容メッシュの例
は、ｎ×ｎ ２次元メッシュの非常に通常の場合であ
る。ここに述べた進め方を用い、ｋの奇数又は偶数に対
し、それぞれ２ｋ＋２又は２ｋ＋４次を有するｋ−ＦＴ
２次元メッシュを構築できる。特に興味がありまた有
用な事例は単一故障を支援するよう設計された故障許容
メッシュの場合である。１−ＦＴ ２次元メッシュはな
お最大４次を有する。すなわち、単一予備ノードを追加
し、次数を多くとも（原メッシュと同じ）４に保持する
ことにより、いかなる単一故障も許容できるアーキテク
チャが得られる。
【００７５】形式的には、典型的なｎ×ｎ ２次元メッ
シュに対する故障許容グラフでは、Ｎ＝ｎ2 ＋１個のノ
ードがある。エッジはオフセット｛１，ｎ｝に従って定
義される。当業者は、これは行優先ラベル付けの拡張で
あると評価するであろう。
【００７６】図−４は（１個までの故障の存在下で）図
−１に描かれたメッシュを含むと保証される４×４ １
−ＦＴ ２次元メッシュの例を描いたものである。図４
のメッシュの１７個のノードは３００〜３１６のラベル
付けされる。メッシュ中の行優先順序位置はノードを表
わす円内に示されている。すなわち、ノード０に始ま
り、位置は０〜１６である。ノード３００〜３１６はそ
れぞれ図−１のノード１００〜１１５に対応し、ノード
３１６は故障許容メッシュにおける「予備」ノードであ
る（図１Ａで画かれたメッシュにはない）。
【００７７】実践を用いて図４に示されたエッジは図−
１に描かれたそれらのエッジに対応する。（図−４で）
点線で示すエッジは故障が支援され、以下に説明する再
命名処理に従ってメッシュを再構成（再ラベル付け）す
る時に用いることがある。
【００７８】図−４に示した故障許容メッシュ（描かれ
たすべてのエッジを含む）は図−５に示すサーキュラン
ト・グラフに対応する。ここでサーキュラント・グラフ
を構築するのに用いたオフセットは１と４とであり、す
べての計算は１７を法として行われる。（予備ノードを
含み１７個のノードがある）。図−４に描かれたすべて
の参照番号、ノード、エッジは図−４に示すものに対応
する。
【００７９】構築処理（すなわち図３Ａに示す故障許容
メッシュに対するモデルとして図−５に示すグラフの構
築）に対する入力は次のとおりである。 (１) 目標メッ
シュの次元ｄ（図１Ａのケースではｄ＝２）、 (２) ｎ
1 ，ｎ2 ，…，ｎd （すなわち、目標メッシュ自体の構
造が入力である。例えば図１Ａのケースではｎ1 ＝ｎ2
＝４）、 (３) 支援さるべき故障数ｋ（図−５に示す故
障許容グラフの構築ではｋ＝１とおいた）。
【００８０】要するに、本発明の一側面によれば、Ｎ＝
ｎ1 ×ｎ2 ×…×ｎd 個の同一ノード（ｄ≧２，ｎｄ≧
３）を有するｄ次元メッシュＭを含む故障許容メッシュ
Ｍｋは、Ｍｋがｋ個までの故障を支援できかつメッシュ
Ｍを形成するのにスイッチを使用せずに再構成できる時
は、次の項を含む、 (ａ) Ｎ＋ｋ個のノード、追加のｋ
個のノードはメッシュＭの場合と同じタイプであり、サ
ーキュラントグラフとして配列されている、 (ｂ) 上記
サーキュラント・グラフに対する複数のエッジ、ここ
で、ｋが奇数の時は、エッジは次のオフセットの組の組
み合わせで定義される。
【００８１】 ｛１＋ｊ 但し ０≦ｊ≦（ｋ−１）／２｝； ｛ｎ1 ＋ｊ 但し ０≦ｊ≦（ｋ−１）／２｝； ｛（ｎ1 ×ｎ2 ）＋ｊ 但し ０≦ｊ≦（ｋ−１）／
２｝；から ｛（ｎ1 ×ｎ2 ×…×ｎd-1 ）＋ｊ 但し ０≦ｊ≦
（ｋ−１）／２｝；まで またｋが偶数の時は、エッジは次のオフセットの組の組
み合わせにより定義される。
【００８２】 ｛１＋ｊ 但し ０≦ｊ≦ｋ／２｝； ｛ｎ1 ＋ｊ 但し ０≦ｊ≦ｋ／２｝； ｛（ｎ1 ×ｎ2 ）＋ｊ 但し ０≦ｊ≦ｋ／２｝；から ｛（ｎ1 ×ｎ2 ×…×ｎd-1 ）＋ｊ 但し ０≦ｊ≦ｋ
／２｝；まで 次に、故障の存在下で故障許容メッシュを再ラベル付け
する系統的方法を述べる。Ｍｋ（ｋ−ＦＴメッシュ）に
ｋ個の故障を与えられて、この再ラベル付け（再命名）
処理の結果は健全な目標メッシュＭの識別である。
【００８３】本処理はノードに新ラベルを割り当てるこ
とにより、健全メッシュを識別（定義）する。この新ラ
ベル付けは健全メッシュの行優先ラベル付けに対応す
る。当業者は、以後説明する本発明の教示に従って構築
される（あるいは提供される）故障許容メッシュを与え
られると、すべての必要なエッジが本処理を実行するの
に存在していることを容易に理解するであろう。
【００８４】更に、本質的に再命名処理に関し、故障し
ているＭｋ中のｋ個のノードは識別され、処理への入力
として提供される。これらノードはＭｋ中の故障してい
る物理的構成部品に対応する。当業者は、以下示される
手法がｋ個の故障が識別され実時間で再命名処理の入力
として示されるか、あるいはオフラインベースでなされ
るかのいずれかとは無関係に効力があることを認めるで
あろう。故障ノード発見の方法および装置は当業者には
充分知られており、本質的には本発明の一部を構成しな
い。
【００８５】ｘ個の故障ノード（ｘ＜ｋ）がある場合に
は、本発明によれば、いかなるｋ−ｘ個の健全ノードは
任意に選ばれ、故障していると考えられる。（Ｍｋに対
応する）サーキュラント・グラフにおけるノードは０か
らＮ＋ｋ−１までの番号付けをすることが出来る点を思
い出すべきである。これらのノードは周期的に順序づけ
られるから、ノードＮ＋ｋ−１と０とは隣接している。
従って、ノードを昇順ｖたどるとノード０はノードＮ＋
ｋ−１の次であり、降順にたどるとノードＮ＋ｋ−１は
ノード０の次である。
【００８６】以下の説明では、ｊ＝ｎ1 ×ｎ2 ×…×ｎ
d-1 が最大オフセットの値であるとする。本発明で考え
られている再命名処理は以降説明するように３ステップ
（あるいはその等価変形）を含まなければならない。
「等価変形」によって本発明の図解による実施例が、例
えば「カウンタ」と参照する時、その値のトラックをカ
ウントし続ける手段はすべて本質的に物理的カウンタの
代りになり得るということ、すべての「カウンタ」が
「増分式」の時、その代りにすべてのカウンタが減分式
であっても等価の結果が得られうるということ、等を意
味する。再命名処理の以下の説明で使用する特別な術語
は説明の目的のみに示され、請求項で以後定義される本
発明の目的を制限することを意図するものではない。
【００８７】上記３ステップ処理の第１ステップは次の
２カウンタを利用する。故障ノードをカウントするステ
ップと、非故障ノードをカウントするステップである。
第１処理ステップによると、以下説明する手順は０≧ｉ
≧Ｎｋ−１のすべてのｉ値に対し実施される。
【００８８】始めは両カウンタはクリアされている（例
えば、０にセットされる）。次に、本発明の一つの実施
例に従うと、ノードはノードｉで始まり降順で巡回され
る。各ノードが巡回されると適当なカウンタは増分され
る。すなわち、もし巡回されたノードが故障なら、故障
ノードに対するカウンタは増分され、また巡回されたノ
ードが非故障なら、非故障ノードに対するカウンタが増
分される。
【００８９】増分された後、非故障ノードに対するカウ
ンタはチェックされる。このカウンタがｊ（ｊ＝ｎ1 ×
ｎ2 ×…×ｎd-1 ということを思い出すこと）より大な
らば、降順でノードを巡回する処理は終り、故障ノード
に対するカウンタがチェックされる。故障ノードに対す
るカウンタがｋ／２より大であれば、ノードｉは「マー
クあり」と呼ばれ、一方ｋ／２より小又は等しければ、
ノードｉは「マーク成し」と呼ばれる。各非故障「マー
クあり」ノードは目標メッシュのノード０に対する候補
である。
【００９０】処理の第２ステップは候補非故障ノードの
いずれが非故障メッシュにおけるノード０の役割を果た
すべきかを決める。第２ステップは単一カウンタを使用
し、２段階よりなる。
【００９１】段階１は、本発明の好ましい実施例によれ
ば、カウンタを０にセットすることにより開始される。
次いで、任意に選ばれたノードを出発点として、ノード
は降順で巡回される。
【００９２】各ノードが巡回されると、ノードはそれが
故障かどうかあるいはマークがあるか否かを調べるため
にチェックされる。もしノードが非故障でマークなしで
あれば、そのカウンタは増分する。ノードが非故障でマ
ークあれば、そのカウンタは０にリセットされる。ノー
ドが故障ならば、そのカウンタはそのままである。
【００９３】次にカウンタがチェックされ、もしカウン
タがＮ／２より大又は等しければ段階１は終了する。カ
ウンタがＮ／２に達した時に巡回されつつあったノード
は、本発明の好ましい実施例ではノードａと称せられ
る。
【００９４】段階２では、ノードはノードａで始まる昇
順で巡回される。マークありの非故障ノードに遭遇する
と段階２は終了する。本発明によれば、この非故障マー
クありノードはノードｂと称される。
【００９５】再命名処理の第３ステップは非故障ノード
に番号（識別子）を割り当てる。ノードｂで始まる昇順
でノードが巡回され、非故障ノードは順に値０，１，
…，Ｎ−１を割り当てられる。従って、ノードｂは０を
割り当てられ、巡回される次ぎの非故障ノードは１を割
り当てられ、巡回された最後の非故障ノードはＮ−１を
割り当てられる。これらの番号は非故障メッシュの行優
先ラベルに対応する。
【００９６】再び、単一故障の場合には、上記処理は故
障直後に始まる新ラベル付けに帰着することに注目すべ
きである。例えば、図−６を参照し、図−４の４×４
１−ＦＴメッシュを考え、ノード３０５が故障している
と仮定してみること。
【００９７】図−６は上に述べた再命名処理の実施後の
メッシュの新ラベル付けを表わす。新メッシュの効力の
あるエッジは実線で示してある。故障ノードを「削除」
（図−６では黒く塗りつぶした円で表す）した後、もう
使用しないエッジは点線で示される。
【００９８】図−６ではｋが１に等しい時、図３Ａのノ
ード３０５の一に対応する）ノード４０５がスイッチあ
るいは（本発明の教示に従って要求される１個の予備ノ
ード以外の）余分のノードを使用せずに削除されること
が分かる。また、再ラベル付け処理の結果として、ノー
ド４０６は今度は図−４に示すメッシュのノード３００
の行優先順の位置を占める（すなわちノード０として）
ことに注目すべきである。再構成されたメッシュでのノ
ード４０６は、原メッシュのノード３１０と同様、２個
のエッジのみを有することにも注目すべきである。
【００９９】メッシュ内の故障許容を達成する上記手法
は、特にｋの値が小さい時、完全に直接的方法で実行で
きる。例えば、単一故障（ｋ＝１）の場合には、１−Ｆ
Ｔメッシュの最大次数は２ｄであり、これは原メッシュ
と同一である。従って、故障許容メッシュはノードの仕
様変更なしに実行できる（与えられたノードからのある
いはノードへの追加の結合は必要でない）。ｋの値が更
に大きい時は、次数の増加を処理するためにスイッチ機
構を使用することが可能である。再び、ｋの値が小さい
時、これは非常に実用的かつ有効な進め方である。
【０１００】Ｎ個（ここで Ｎ＝ｎ1 ×ｎ2 ×…ｎd、
また ｎ≧２，ｎd ≧３）のノードを有するｄ次元目標
メッシュＭを与えられた時、ｋ個の故障許容メッシュＭ
ｋを構築する処理の流れ図表示である図５を、ここで参
照しなければならない。
【０１０１】図７のブロック５０１は本発明で想定して
いる構築処理に必要な入力を示している。示されている
個々の値については上記で既に詳細に説明した。
【０１０２】ブロック５０２〜５０４は、今まで説明し
たサーキュラントグラフ作成のステップを表わしてお
り、グラフは（ｎ1 ×ｎ2 ×…ｎd ）＋ｋ個のノードを
有し、またグラフのオフセットはｋの値（奇数か偶数
か）に依存する。
【０１０３】ブロック５０５は出力の故障許容メッシュ
を表わす。すなわち５０３か５０４の適当な方で構築さ
れたグラフモデルに従い組み立てることが出来るｋ個の
故障許容メッシュＭを表わす。
【０１０４】目標メッシュＭを探し出すのにｋ個までの
故障の存在下でＫ故障許容メッシュＭｋの再ラベル付け
に関するプロセスの流れ図表示である図８を参照しなけ
ればならない。
【０１０５】ブロック６０１は予め決められた順にサー
キュラントグラフのノードが巡回された場合、各非故障
ノードがマークありか、マークなしかを定めるステップ
を表わす。
【０１０６】ブロック６０２はどの非故障マークありの
ノードが目標メッシュでノード０の役割を果たすべきか
を定めるステップを表わす。
【０１０７】ブロック６０３は新規の残処理中の最終ス
テップを表わす、すなわちノード０から始まる各非故障
ノードに識別子を割り当てるステップであり、ここで識
別子の組は再構築されたメッシュの行優先順序づけを表
わす。
【０１０８】これまで述べたことは、前に説明したすべ
ての目的に合致するメッシュ・アーキテクチャにおける
故障を許容するための方法と装置である。当業者は、前
記の記述が図解と説明のみの目的で示されたことを認め
るであろう。包括的であること、あるいは開示された厳
密な形に本発明を制限することを意図するものでなく、
また明かに多くの変更態様および変形が上記教示に徴し
て、可能である。
【図面の簡単な説明】
【図１】４行４列（１６ノード）を有する従来技術の２
次元メッシユの実施例を示す図。
【図２】図１に示したメッシュを、予備構成部品（４個
の余分な同一ノード）の追加により、ある場合には回収
メッシュが故障許容であるように回収するための従来技
術の手法を示す図。
【図３】図１に示すメッシュと同様、４×４ ２次元メ
ッシュに対応するサーキュラントグラフの実施例を示す
図。
【図４】Ｋ＝１の場合に本発明の教示に従って伝えられ
るｋ個の故障許容４×４メッシュを示す図。
【図５】図４に示す故障許容メッシュを構築できるサー
キュラント・グラフ・モデルであって、本発明の教示に
従って、図示サーキュラント・グラフを構築するのに用
いた与えられた目標メッシュが図１に示すメッシュであ
る場合のサーキュラント・グラフ・モデル。
【図６】図４に示す（単一故障発生後の）故障許容メッ
シュの再構成版であって、スイッチを使用せず、本発明
の再命名処理部分に従って再構成が実施されている場合
の再構成版。
【図７】Ｎ個の（Ｎ＝ｎ1 ×ｎ2 ×…ｎd 、ｎ≧２，ｎ
d ≧３）のノードを有するα次元目標メッシュＭが与え
られた時に、ｋ個の故障許容メッシュＭｋを構築する処
理の流れ図。
【図８】目標メッシュＭを探し出すため、ｋ個までの故
障の存在下で、ｋ個の故障許容メッシュの再ラベル付け
に対する処理の流れ図。
【符号の説明】
１００〜１１５ ノード １２０〜１２３ 予備ノード ２００〜２１５ ノード ２５０〜２５６ エッジ ３００〜３１５ ノード ３１６ 予備ノード ４００〜４１６ ノード ５０１〜５０５ ブロック ６０１〜６０３ ブロック
───────────────────────────────────────────────────── フロントページの続き (72)発明者 ロバート、イー、サイフアー アメリカ合衆国カリフオルニア州、ロスガ トス、ベラ、ビスタ、アベニユ、344 (72)発明者 チン‐テイエン、ホ アメリカ合衆国カリフオルニア州、サンノ ゼ、アンジヨー、クリーク、サークル、 7055

Claims (10)

    【特許請求の範囲】
  1. 【請求項１】ｋ個までの故障を支援可能であり、かつメ
    ッシュＭを形成するのにスイッチなしで再構成可能なよ
    うに、Ｎ＝ｎ1 ×ｎ2 ×…×ｎ個（但しｄ≧２、ｎｄ≧
    ３）の同一ノードを有するｄ次元メッシュＭを含む故障
    許容メッシュＭｋであって、 (a) サーキュラント・グラフ形式で配置され、追加ｋ
    個のノードがメッシュＭにおけるのと同一タイプである
    ようなＮ＋ｋ個のノードと、 ならびに (b) ｋが奇数の時は、エッジが次のオフセットの組の
    組み合せ ｛１＋ｊ但し０≦ｊ≦（ｋ−１）／２｝； ｛ｎ1 ＋ｊ但し０≦ｊ≦（ｋ−１）／２｝； ｛（ｎ1 ×ｎ2 ）＋ｊ但し０≦ｊ≦（ｋ−１）／２｝；
    から ｛（ｎ1 ×ｎ2 ×…×ｎｄ−１）＋ｊ但し０≦ｊ≦（ｋ
    −１）／２｝；まで により定義され、またｋが偶数の時は、エッジが次のオ
    フセットの組の組み合わせ、 ｛１＋ｊ但し０≦ｊ≦ｋ／２｝； ｛ｎ1 ＋ｊ但し０≦ｊ≦ｋ／２｝； ｛（ｎ1 ×ｎ2 ）＋ｊ但し０≦ｊ≦ｋ／２｝；から ｛（ｎ1 ×ｎ2 ×…×ｎｄ−１）＋ｊ但し０≦ｊ≦ｋ／
    ２｝；まで により定義される前記サーキュラントグラフに対する複
    数のエッジとを有することを特徴とする故障許容メッシ
    ュ。
  2. 【請求項２】ｋ個の故障許容メッシュＭｋを構築するた
    めの方法であって、 (a) Ｎ個（Ｎ＝ｎ1 ×ｎ2 ×…×ｎｄ、但しｄ≧２、
    ｎｄ≧３）のノードおよび前記サーキュラント・グラフ
    に含まれるべきｋ個の追加ノード（但し、ｋはＭｋ組み
    立て用のモデルとしてＭｋに支援されるべき最大数の故
    障に正確に等しい場合）を有するｄ次元メッシュＭを与
    えられた時にサーキュラント・グラフ表示を利用するス
    テップと、 (b) 上記サーキュラント・グラフモデルに基づくｋ個
    の故障許容メッシュＭｋを組み立てるステップ とを有することを特徴とする方法。
  3. 【請求項３】ｋ個までの故障を支援可能であり、かつメ
    ッシュＭを形成するためにスイッチなしで再構成可能な
    ように、Ｎ＝ｎ1 ×ｎ2 ×…×ｎｄ個（但しｄ≧２、ｎ
    ｄ≧３）の同一ノードを有するｄ次元メッシュＭを含む
    ｋ個の故障許容メッシュＭｋを構築する方法であって、 (a) Ｎ個のノードならびに追加のｋ個のノードがサー
    キュラント・グラフ形式で、メッシュＭにおけるのと同
    一タイプであるように、正確にｋ個の追加ノードを配置
    するステップと、 (b) 前記サーキュラント・グラフのエッジを、ｋが奇
    数の場合は次のオフセットの組の組み合わせ ｛１＋ｊ但し０≦ｊ≦（ｋ−１）／２｝； ｛ｎ1 ＋ｊ但し０≦ｊ≦（ｋ−１）／２｝； ｛（ｎ1 ×ｎ2 ）＋ｊ但し０≦ｊ≦（ｋ−１）／２｝；
    から ｛（ｎ1 ×ｎ2 ×…×ｎｄ−１）＋ｊ但し０≦ｊ≦（ｋ
    −１）／２｝；まで により定義するステップと、 (a) 上記サーキュラント・グラフのエッジを、ｋが偶
    数の場合は次のオフセットの組の組み合わせ ｛１＋ｊ但し０≦ｊ≦ｋ／２｝； ｛ｎ1 ＋ｊ但し０≦ｊ≦ｋ／２｝； ｛（ｎ1 ×ｎ2 ）＋ｊ但し０≦ｊ≦ｋ／２｝；から ｛（ｎ1 ×ｎ2 ×…×ｎｄ−１）＋ｊ但し０≦ｊ≦ｋ／
    ２｝；まで により定義するステップと、 を有することを特徴とする方法。
  4. 【請求項４】Ｎ＝ｎ1 ×ｎ2 ×…×ｎｄ個（但しｄ≧
    ２、ｎｄ≧３）のノードを有するいかなるｄ次元メッシ
    ュでもよい目標メッシュＭが与えられた時、ｄ次元ｋ故
    障許容メッシュＭｋを組みたてる方法であって、 (a) 目標メッシュＭの次元ｄを決定するステップと、 (b) ｎ1 ，ｎ2 …ｎｄの値を入力することにより、目
    標メッシュＭの構造を識別するステップと、 (c) 構築されるべき故障許容メッシュＭｋにより支援
    される故障数ｋを入力するステップと、 (d) 正確にＮ＋Ｋ個のノードを有するサーキュラント
    グラフを定義するステップと、 (e) ｋが奇数の時、次のオフセットの組の組み合わせ ｛１＋ｊ但し０≦ｊ≦（ｋ−１）／２｝； ｛ｎ1 ＋ｊ但し０≦ｊ≦（ｋ−１）／２｝； ｛（ｎ1 ×ｎ2 ）＋ｊ但し０≦ｊ≦（ｋ−１）／２｝；
    から ｛（ｎ1 ×ｎ2 ×…×ｎｄ−１）＋ｊ但し０≦ｊ≦（ｋ
    −１）／２｝；まで により前記サーキュラント・グラフのエッジを定義する
    ステップと、 (f) ｋが偶数の時は、次のオフセットの組の組み合わ
    せ ｛１＋ｊ但し０≦ｊ≦ｋ／２｝； ｛ｎ1 ＋ｊ但し０≦ｊ≦ｋ／２｝； ｛（ｎ1 ×ｎ2 ）＋ｊ但し０≦ｊ≦ｋ／２｝；から ｛（ｎ1 ×ｎ2 ×…×ｎｄ−１）＋ｊ但し０≦ｊ≦ｋ／
    ２｝；まで により前記サーキュラント・グラフのエッジを定義する
    ステップと、 (d) ｄ次元ｋ故障許容メッシュＭｋを形成するため
    に、上記サーキュラント・グラフに対応するメッシュを
    構築するステップと、 を有することを特徴とする方法。
  5. 【請求項５】ｋ個の故障の存在下で故障許容メッシュＭ
    ｋ中に健全な目標メッシュＭを探し出し、および(1) Ｍ
    の次元ｄ、(2) ｋの値、(3) ｎ1 、ｎ2 …ｎｄの値（こ
    こで格ｎｄはｄ次元メッシュの辺の長さでｄ≧２、ｎｄ
    ≧３）、(4) サーキュラント・グラフ・モデルに基づく
    故障許容メッシュＭｋの構造、および(5) Ｍｋ中のｋ個
    までの故障の位置、を与えられ、Ｍを得るためにＭｋの
    再構成のための方法であって、 (a) Ｍｋで支援される故障数がｋより小さいかどうか
    を決定するステップと、 (b) ｋ−ｘ個の非故障ノードを選定し、ｋ個の故障ノ
    ードの全体に対し、もしｘ＜ｋならｋ−ｘ個のノードを
    故障と指示するステップと、 (c) Ｍｋに残っている非故障ノードの中から目標メッ
    シュＭ中のノード０を識別するステップと、 (d) ノード０で始まる行優先順序づけを用いて、健全
    なメッシュＭを得るためにＭｋ中のノードを再ラベルづ
    けするステップと、 を有することを特徴とする方法。
  6. 【請求項６】故障許容メッシュＭｋがＮ＋ｋ＝（ｎ1 ×
    ｎ2 ×…×ｎｄ）＋ｋ個（但しｄ≧２、ｎｄ≧３）のノ
    ードを有し、健全メッシュＭがＮ個のノードを有する場
    合、ｋ個までの故障の組を与えられて、故障許容メッシ
    ュＭｋ中に健全メッシュＭを発見する方法であって、 (a) 故障許容メッシュＭｋ中の非故障ノードがメッシ
    ュＭのノード０の候補と考えられるべきかどうかを決定
    するステップと、 (b) いずれの候補非故障ノードが目標メッシュのノー
    ド０であるべきかを決定するステップと、 (c) 識別子の組がメッシュＭの行優先順序づけを表わ
    すように、ノード０から始めて、各非故障ノードを有す
    ることを特徴とする方法。
  7. 【請求項７】サーキュラント・グラフ・モデルで表わす
    ことが可能であり、かつこのグラフ中の最大オフセット
    がｊ＝ｎ1 ×ｎ2 ×…×ｎｄ−１であるように、ｋ個ま
    での故障を支援していたｋ故障許容メッシュＭｋ中に、
    Ｎ個（但しＮ＝ｎ1 ×ｎ2 ×…×ｎｄ、ｄ≧２、ｎｄ≧
    ３）のノードを有するｄ次元目標メッシュＭを探し出す
    処理方法であって、 (a) Ｍｋ中の各故障および非故障ノードの識別ならび
    にそのサーキュラント・グラフを入力するステップと、 (b) ノードｉで始まり、サーキュラントグラフの周囲
    を最初の事前選定方向に進めて各ノードを巡回すること
    により、Ｍｋ中のすべてのノードｉ（但し０≦ｉ≦Ｎ＋
    Ｋ−１）に対し、Ｍｋ中の故障ノードおよび非故障ノー
    ドの数をカウントするステップと、 (c) 各非故障ノードの検出後に非故障ノードのカウン
    トをチェックし、その非故障ノードのカウントがｊより
    大かどうかを決定するステップと、 (d) その非故障ノードの数がｊより大であれば、上記
    最初の事前選定方向でのノード巡回を終了するステップ
    と、 (e) 前記終了のステップの後で、故障ノードの数がｋ
    ／２より大であるかどうかを決定し、もし大であればノ
    ードｉをマークありのノードと指定し、またもし大でな
    ければノードｉをマークなしと指定するステップと、 (f) メッシュＭｋ中の各ノードｉ（但し０≦ｉ≦Ｎ＋
    ｋ−１）に対し、上述の処理を繰返すステップと、 を有することを特徴とする方法。
  8. 【請求項８】ｋ個までの故障を支援可能で、かつメッシ
    ュＭを形成するのにスイッチを使用せずに再構成可能な
    ように、Ｎ＝ｎ1 ×ｎ2 ×…×ｎｄ個（但しｄ≧２、ｎ
    ｄ≧３）の同一ノードを有するｄ次元メッシュＭを含む
    ｋ故障許容メッシュＭｋの構築、およびｋ個までの故障
    がＭｋにより支援される時に、Ｍｋ中にＭを捜し出す方
    法であって、 (a) メッシュＭのＮ個のノードおよびサーキュラント
    ・グラフ形式で追加ｋ個のノードがメッシュにおけるの
    と同一タイプであるように、正確にｋ個の追加ノードを
    配列するステップと、 (b) ｋが奇数の時に、次のオフセットの組の組み合わ
    せ ｛１＋ｊ但し０≦ｊ≦ｋ／２｝； ｛ｎ1 ＋ｊ但し０≦ｊ≦ｋ／２｝； ｛（ｎ1 ×ｎ2 ）＋ｊ但し０≦ｊ≦ｋ／２｝；から ｛（ｎ1 ×ｎ2 ×…×ｎｄ−１）＋ｊ但し０≦ｊ≦ｋ／
    ２｝；まで により前記サーキュラント・グラフのエッジを定義する
    ステップと、 (c) ｋが偶数の時に、次のオフセットの組の組み合わ
    せ ｛１＋ｊ但し０≦ｊ≦ｋ／２｝； ｛ｎ1 ＋ｊ但し０≦ｊ≦ｋ／２｝； ｛（ｎ1 ×ｎ2 ）＋ｊ但し０≦ｊ≦ｋ／２｝；から ｛（ｎ1 ×ｎ2 ×…×ｎｄ−１）＋ｊ但し０≦ｊ≦ｋ／
    ２｝；まで により前記サーキュラント・グラフのエッジを定義する
    ステップと、 (d) Ｍｋがｋ個の故障を支援している時、Ｍｋ中のい
    ずれの非故障ノードがノード０に対する候補と考えられ
    るべきかを決定するステップと、 (e) 候補非故障ノードのいずれが目標メッシュＭ中の
    ノード０であるべきかを決定するステップと、 (f) 識別子の組がメッシュＭの業優先順序づけを表わ
    すよう、ノード０で開始し、各非故障ノードに識別子を
    割り当てるステップとを有することを特徴とする方法。
  9. 【請求項９】故障許容メッシュＭｋがＮ＋ｋ＝（ｎ1 ×
    Ｎ2 ×…×ｎｄ）＋ｋ個（但しｄ≧２、ｎｄ≧３）のノ
    ードを有し、また健全メッシュＭがＮ個のノードを有す
    る時に、ｋ個までの故障の組を与えられ、故障許容メッ
    シュＭｋ中に健全メッシュＭを識別するための装置であ
    って、 (a) メッシュＭｋ中のいずれの非故障ノードがメッシ
    ュＭ中のノード０に対する候補と考えらべきかどうかを
    識別する手段と、 (b) 決定のための方法が識別のための上記方法からの
    入力に応答する時、候補非故障ノードのいずれが目標メ
    ッシュ中のノード０であるべきかを決定する手段と、 (c) ノード０で始まり、識別子の組がメッシュＭの業
    優先順序づけを表わす時に、前記判別のための方法によ
    って識別されるように、メッシュＭｋ中の各非故障ノー
    ドに識別子を割り当てるための再構成の手段と、 を有することを特徴とする装置。
  10. 【請求項１０】請求項９記載の装置において、ｋ個まで
    の故障の存在下で、上記Ｍｋがスイッチの使用なしに健
    全目標メッシュＭ中に再構成することのできることを特
    徴とする装置。
JP4099996A 1991-06-28 1992-04-20 メッシュアーキテクチャにおける故障許容のための方法と装置 Expired - Lifetime JP2620457B2 (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US07/723,287 US5280607A (en) 1991-06-28 1991-06-28 Method and apparatus for tolerating faults in mesh architectures
US723287 2003-11-26

Publications (2)

Publication Number Publication Date
JPH05130101A true JPH05130101A (ja) 1993-05-25
JP2620457B2 JP2620457B2 (ja) 1997-06-11

Family

ID=24905615

Family Applications (1)

Application Number Title Priority Date Filing Date
JP4099996A Expired - Lifetime JP2620457B2 (ja) 1991-06-28 1992-04-20 メッシュアーキテクチャにおける故障許容のための方法と装置

Country Status (2)

Country Link
US (1) US5280607A (ja)
JP (1) JP2620457B2 (ja)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2005539312A (ja) * 2002-09-13 2005-12-22 ドコモ コミュニケーションズ ラボラトリーズ ユー・エス・エー インコーポレーティッド フォールトトレランススキームを動的に切換えるための方法

Families Citing this family (32)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP1046994A3 (en) * 1994-03-22 2000-12-06 Hyperchip Inc. Efficient direct cell replacement fault tolerant architecture supporting completely integrated systems with means for direct communication with system operator
US5590356A (en) * 1994-08-23 1996-12-31 Massachusetts Institute Of Technology Mesh parallel computer architecture apparatus and associated methods
US5603044A (en) * 1995-02-08 1997-02-11 International Business Machines Corporation Interconnection network for a multi-nodal data processing system which exhibits incremental scalability
US6467046B1 (en) * 1996-05-06 2002-10-15 Sun Microsystems, Inc. System and method for automatically distributing copies of a replicated database in a computer system
US5859983A (en) * 1996-07-01 1999-01-12 Sun Microsystems, Inc Non-hypercube interconnection subsystem having a subset of nodes interconnected using polygonal topology and other nodes connect to the nodes in the subset
KR980010717A (ko) * 1996-07-24 1998-04-30 김광호 정전기에 의한 시스템 오동작 방지방법
US5912893A (en) * 1997-03-21 1999-06-15 International Business Machines Corporation Incidence graph based communications and operations method and apparatus for parallel processing architecture
US6108340A (en) * 1997-03-21 2000-08-22 International Business Machines Corporation Incidence graph based communications and operations method and apparatus for parallel processing architecture
US5881304A (en) * 1997-03-21 1999-03-09 International Business Machines Corporation Incidence graph based communications and operations method and apparatus for parallel processing architecture
US6456588B1 (en) * 1997-04-21 2002-09-24 At&T Corp. Hypercube routing and restoration in telecommunications networks
US6055225A (en) * 1997-06-02 2000-04-25 Hewlett-Packard Company Ring architecture for quad port bypass circuits
US6178522B1 (en) 1998-06-02 2001-01-23 Alliedsignal Inc. Method and apparatus for managing redundant computer-based systems for fault tolerant computing
US9178784B2 (en) 2004-04-15 2015-11-03 Raytheon Company System and method for cluster management based on HPC architecture
US20050235055A1 (en) * 2004-04-15 2005-10-20 Raytheon Company Graphical user interface for managing HPC clusters
US7711977B2 (en) * 2004-04-15 2010-05-04 Raytheon Company System and method for detecting and managing HPC node failure
US8336040B2 (en) 2004-04-15 2012-12-18 Raytheon Company System and method for topology-aware job scheduling and backfilling in an HPC environment
US8190714B2 (en) * 2004-04-15 2012-05-29 Raytheon Company System and method for computer cluster virtualization using dynamic boot images and virtual disk
US8335909B2 (en) * 2004-04-15 2012-12-18 Raytheon Company Coupling processors to each other for high performance computing (HPC)
US7958208B2 (en) * 2004-09-22 2011-06-07 At&T Intellectual Property I, L.P. System and method for designing a customized switched metro Ethernet data network
US7475274B2 (en) 2004-11-17 2009-01-06 Raytheon Company Fault tolerance and recovery in a high-performance computing (HPC) system
US7433931B2 (en) * 2004-11-17 2008-10-07 Raytheon Company Scheduling in a high-performance computing (HPC) system
US8244882B2 (en) * 2004-11-17 2012-08-14 Raytheon Company On-demand instantiation in a high-performance computing (HPC) system
TW200712898A (en) * 2005-09-30 2007-04-01 Tyan Computer Corp Multi-processor module
US7958341B1 (en) 2008-07-07 2011-06-07 Ovics Processing stream instruction in IC of mesh connected matrix of processors containing pipeline coupled switch transferring messages over consecutive cycles from one link to another link or memory
US8145880B1 (en) * 2008-07-07 2012-03-27 Ovics Matrix processor data switch routing systems and methods
US8327114B1 (en) 2008-07-07 2012-12-04 Ovics Matrix processor proxy systems and methods
US8131975B1 (en) * 2008-07-07 2012-03-06 Ovics Matrix processor initialization systems and methods
TWI410087B (zh) 2010-12-20 2013-09-21 Ind Tech Res Inst 多核心晶片網路
JP2014215914A (ja) * 2013-04-26 2014-11-17 株式会社東芝 端末装置、情報処理方法及び情報処理プログラム
CN107018080B (zh) * 2017-03-22 2020-04-07 上海海事大学 一种考虑节点能量的延迟容忍网络拓扑路由方法
CN117785567B (zh) * 2024-02-28 2024-05-28 上海特高信息技术有限公司 一种基于连接方向的可重构容错策略及重构控制器
US12493503B2 (en) * 2024-04-17 2025-12-09 Dell Products L.P. Hypercube topology for byzantine fault tolerant solutions to reduce network communication overhead of PBFT-based protocols

Family Cites Families (28)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4047163A (en) * 1975-07-03 1977-09-06 Texas Instruments Incorporated Fault-tolerant cell addressable array
US4051354A (en) * 1975-07-03 1977-09-27 Texas Instruments Incorporated Fault-tolerant cell addressable array
US4295218A (en) * 1979-06-25 1981-10-13 Regents Of The University Of California Error-correcting coding system
US4302819A (en) * 1979-10-22 1981-11-24 Hewlett-Packard Company Fault tolerant monolithic multiplier
NL8002787A (nl) * 1980-05-14 1981-12-16 Philips Nv Multiprocessor-rekenmachinesysteem voor het uitvoeren van een recursief algorithme.
US4507726A (en) * 1982-01-26 1985-03-26 Hughes Aircraft Company Array processor architecture utilizing modular elemental processors
CA1219965A (en) * 1983-04-11 1987-03-31 Allen P. Clarke Self repair large scale integrated circuit
US4605928A (en) * 1983-10-24 1986-08-12 International Business Machines Corporation Fault-tolerant array of cross-point switching matrices
US4922408A (en) * 1985-09-27 1990-05-01 Schlumberger Technology Corporation Apparatus for multi-processor communications
US4722084A (en) * 1985-10-02 1988-01-26 Itt Corporation Array reconfiguration apparatus and methods particularly adapted for use with very large scale integrated circuits
US4783782A (en) * 1985-12-12 1988-11-08 Alcatel U.S.A. Corporation Manufacturing test data storage apparatus for dynamically reconfigurable cellular array processor chip
NL8600218A (nl) * 1986-01-30 1987-08-17 Philips Nv Netwerk van dataverwerkingsstations.
GB8605367D0 (en) * 1986-03-05 1986-04-09 Secr Defence Bit-slice digital processor
US4791603A (en) * 1986-07-18 1988-12-13 Honeywell Inc. Dynamically reconfigurable array logic
US5038386A (en) * 1986-08-29 1991-08-06 International Business Machines Corporation Polymorphic mesh network image processing system
FR2606184B1 (fr) * 1986-10-31 1991-11-29 Thomson Csf Dispositif de calcul reconfigurable
JP2629697B2 (ja) * 1987-03-27 1997-07-09 日本電気株式会社 半導体記憶装置
DE3853860D1 (de) * 1987-09-22 1995-06-29 Siemens Ag Vorrichtung zur Herstellung einer testkompatiblen, weitgehend fehlertoleranten Konfiguration von redundant implementierten systolischen VLSI-Systemen.
US4868818A (en) * 1987-10-29 1989-09-19 The United States Of America As Represented By The Administrator Of The National Aeronautics And Space Administration Fault tolerant hypercube computer system architecture
US4907232A (en) * 1988-04-28 1990-03-06 The Charles Stark Draper Laboratory, Inc. Fault-tolerant parallel processing system
US4970724A (en) * 1988-12-22 1990-11-13 Hughes Aircraft Company Redundancy and testing techniques for IC wafers
US5020059A (en) * 1989-03-31 1991-05-28 At&T Bell Laboratories Reconfigurable signal processor
DE3916720A1 (de) * 1989-05-23 1990-11-29 Ant Nachrichtentech Verfahren zur erweiterung eines dreistufigen regelmaessigen koppelfeldes
US5088091A (en) * 1989-06-22 1992-02-11 Digital Equipment Corporation High-speed mesh connected local area network
US5134690A (en) * 1989-06-26 1992-07-28 Samatham Maheswara R Augumented multiprocessor networks
US5133073A (en) * 1990-05-29 1992-07-21 Wavetracer, Inc. Processor array of N-dimensions which is physically reconfigurable into N-1
US5173689A (en) * 1990-06-25 1992-12-22 Nec Corporation Self-distributed logical channel node failure restoring system
US5271014A (en) 1992-05-04 1993-12-14 International Business Machines Corporation Method and apparatus for a fault-tolerant mesh with spare nodes

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2005539312A (ja) * 2002-09-13 2005-12-22 ドコモ コミュニケーションズ ラボラトリーズ ユー・エス・エー インコーポレーティッド フォールトトレランススキームを動的に切換えるための方法

Also Published As

Publication number Publication date
JP2620457B2 (ja) 1997-06-11
US5280607A (en) 1994-01-18

Similar Documents

Publication Publication Date Title
JPH05130101A (ja) メツシユアーキテクチヤにおける故障許容のための方法と装置
Jou et al. Fault-tolerant matrix arithmetic and signal processing on highly concurrent computing structures
US5271014A (en) Method and apparatus for a fault-tolerant mesh with spare nodes
Xu Topological structure and analysis of interconnection networks
Malluhi et al. The hierarchical hypercube: A new interconnection topology for massively parallel systems
Kuo et al. Efficient reconfiguration algorithms for degradable VLSI/WSI arrays
US5513313A (en) Method for generating hierarchical fault-tolerant mesh architectures
JPH0766718A (ja) プログラム可能論理用ウェファ・スケール構造
Kumar et al. Design and analysis of fault-tolerant multistage interconnection networks with low link complexity
Bruck et al. Fault-tolerant de Bruijn and shuffle-exchange networks
Fernández et al. Efficient VLSI layouts for homogeneous product networks
Kothari et al. The kappa network with fault-tolerant destination tag algorithm
Shih et al. Adding multiple-fault tolerance to generalized cube networks
Siegel et al. An introduction to the multistage cube family of interconnection networks
Leu et al. A fault-tolerant tree communication scheme for hypercube systems
Ali et al. Exact bounds on running ASCEND/DESCEND and FAN-IN algorithms on synchronous multiple bus networks
Bertossi et al. A gracefully degradable VLSI system for linear programming
Dutt et al. A local-sparing design methodology for fault-tolerant multiprocessors
Ku et al. Systematic design of fault-tolerant multiprocessors with shared buses
Boubekeur et al. A full experience of designing a wafer scale 2D array
Wang et al. A new fault-tolerant broadcast routing algorithm on mesh networks
Bruck et al. Tolerating faults in a mesh with a row of spare nodes
Mazumder Layout optimisation for yield enhancement in on-chip-VLSI/WSI parallel processing
Varman et al. A robust matrix-multiplication array
Horiguchi et al. Self-reconfiguration scheme of 3D-mesh arrays