JPH0616270B2 - 自己補修形大規模集積回路 - Google Patents
自己補修形大規模集積回路Info
- Publication number
- JPH0616270B2 JPH0616270B2 JP59501474A JP50147484A JPH0616270B2 JP H0616270 B2 JPH0616270 B2 JP H0616270B2 JP 59501474 A JP59501474 A JP 59501474A JP 50147484 A JP50147484 A JP 50147484A JP H0616270 B2 JPH0616270 B2 JP H0616270B2
- Authority
- JP
- Japan
- Prior art keywords
- spe
- spes
- functional
- path
- data
- 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.)
- Expired - Lifetime
Links
- 238000012545 processing Methods 0.000 claims description 19
- 238000000034 method Methods 0.000 claims description 10
- 238000012360 testing method Methods 0.000 claims description 8
- 238000012546 transfer Methods 0.000 claims description 3
- 230000000903 blocking effect Effects 0.000 claims description 2
- 238000000348 solid-phase epitaxy Methods 0.000 claims 30
- 230000005540 biological transmission Effects 0.000 claims 4
- 238000004220 aggregation Methods 0.000 claims 1
- 230000002776 aggregation Effects 0.000 claims 1
- 230000000977 initiatory effect Effects 0.000 claims 1
- 230000000877 morphologic effect Effects 0.000 claims 1
- 239000011159 matrix material Substances 0.000 description 15
- 239000000047 product Substances 0.000 description 7
- 238000001514 detection method Methods 0.000 description 5
- 238000004519 manufacturing process Methods 0.000 description 4
- 238000004458 analytical method Methods 0.000 description 3
- 238000004364 calculation method Methods 0.000 description 3
- 101100366322 Arabidopsis thaliana ADC1 gene Proteins 0.000 description 2
- 101100366333 Arabidopsis thaliana ADC2 gene Proteins 0.000 description 2
- 101150032645 SPE1 gene Proteins 0.000 description 2
- 101150089804 SPE2 gene Proteins 0.000 description 2
- 238000009825 accumulation Methods 0.000 description 2
- 238000003491 array Methods 0.000 description 2
- 230000002457 bidirectional effect Effects 0.000 description 2
- 238000012774 diagnostic algorithm Methods 0.000 description 2
- 229940050561 matrix product Drugs 0.000 description 2
- 230000008569 process Effects 0.000 description 2
- 230000000644 propagated effect Effects 0.000 description 2
- 238000011084 recovery Methods 0.000 description 2
- 230000009467 reduction Effects 0.000 description 2
- 238000000638 solvent extraction Methods 0.000 description 2
- 101100478119 Caenorhabditis elegans spe-6 gene Proteins 0.000 description 1
- PEDCQBHIVMGVHV-UHFFFAOYSA-N Glycerine Chemical compound OCC(O)CO PEDCQBHIVMGVHV-UHFFFAOYSA-N 0.000 description 1
- 101100366397 Saccharomyces cerevisiae (strain ATCC 204508 / S288c) SPE3 gene Proteins 0.000 description 1
- 230000004913 activation Effects 0.000 description 1
- 230000003044 adaptive effect Effects 0.000 description 1
- BFPSDSIWYFKGBC-UHFFFAOYSA-N chlorotrianisene Chemical compound C1=CC(OC)=CC=C1C(Cl)=C(C=1C=CC(OC)=CC=1)C1=CC=C(OC)C=C1 BFPSDSIWYFKGBC-UHFFFAOYSA-N 0.000 description 1
- 238000012790 confirmation Methods 0.000 description 1
- 230000001186 cumulative effect Effects 0.000 description 1
- 230000007547 defect Effects 0.000 description 1
- 230000002950 deficient Effects 0.000 description 1
- 230000000593 degrading effect Effects 0.000 description 1
- 238000002405 diagnostic procedure Methods 0.000 description 1
- 238000010586 diagram Methods 0.000 description 1
- 238000005315 distribution function Methods 0.000 description 1
- 238000005516 engineering process Methods 0.000 description 1
- 230000006872 improvement Effects 0.000 description 1
- 230000000737 periodic effect Effects 0.000 description 1
- 230000001902 propagating effect Effects 0.000 description 1
- 238000011160 research Methods 0.000 description 1
- 230000004044 response Effects 0.000 description 1
- 238000010187 selection method Methods 0.000 description 1
- 239000013589 supplement Substances 0.000 description 1
Classifications
-
- G—PHYSICS
- G11—INFORMATION STORAGE
- G11C—STATIC STORES
- G11C29/00—Checking stores for correct operation ; Subsequent repair; Testing stores during standby or offline operation
- G11C29/006—Checking stores for correct operation ; Subsequent repair; Testing stores during standby or offline operation at wafer scale level, i.e. wafer scale integration [WSI]
Landscapes
- Hardware Redundancy (AREA)
- Multi Processors (AREA)
- Design And Manufacture Of Integrated Circuits (AREA)
Description
【発明の詳細な説明】 概説 ソナー信号処理タスクは、現在使われている本体コンピ
ユータの容量を越える所望の演算負荷と共に、高い入／
出力データ速度によって特徴付けられる。ビーム形成、
波、表示画質の向上等各種タスク用の適応アルゴリズ
ムは、Acoustical Society of America誌等の雑誌文献
で広く議論されている。これらは、ターゲットの検知や
追跡の点でソナーシステムの性能を著しく高める能力が
あるため、実際の環境化において必要である。しかし、
それらアルゴリズムは、演算負荷を大きく増加させる。
所望の演算負荷をある程度満せる幾つかのプロセッサを
結線して所望演算を実行することは、プロセッサが設置
される可動台上のスペース不足のため、その規模が制約
されている。
ユータの容量を越える所望の演算負荷と共に、高い入／
出力データ速度によって特徴付けられる。ビーム形成、
波、表示画質の向上等各種タスク用の適応アルゴリズ
ムは、Acoustical Society of America誌等の雑誌文献
で広く議論されている。これらは、ターゲットの検知や
追跡の点でソナーシステムの性能を著しく高める能力が
あるため、実際の環境化において必要である。しかし、
それらアルゴリズムは、演算負荷を大きく増加させる。
所望の演算負荷をある程度満せる幾つかのプロセッサを
結線して所望演算を実行することは、プロセッサが設置
される可動台上のスペース不足のため、その規模が制約
されている。
こうした矛盾する要求する解決するために必要なこと
は、ソフトウエアのアルゴリズムを、ハードウエアの有
効な実現性に合致させることである。従来このことは、
上記のような専用のハードウエアを意味した。しかし、
こうしてハードウエアは故障時に再構成するのが容易で
ない。システム中の一部の故障は、その部分の手作業交
換を意味する。故障の診断と部品の交換の両方をオペレ
ータが行うことは、現在の環境下において受入れられな
い。
は、ソフトウエアのアルゴリズムを、ハードウエアの有
効な実現性に合致させることである。従来このことは、
上記のような専用のハードウエアを意味した。しかし、
こうしてハードウエアは故障時に再構成するのが容易で
ない。システム中の一部の故障は、その部分の手作業交
換を意味する。故障の診断と部品の交換の両方をオペレ
ータが行うことは、現在の環境下において受入れられな
い。
高性能な専用コンピユータシステムの分野における最近
の研究は、今後のソナープロセッサがシストリック（sy
stolic）アーキテクチャを採用することになろうと指摘
している。これによるとソフトウエアは、各エレメント
が最も隣接のものとのみ接続されたシストリック処理エ
レメント（ＳＰＥ）の多次元的なＶＬＳＩアレイ上で実
行される。このようなアーキテクチャに関する説明は、
その応用や性能と共に、下記を含め多くの筆者によって
成されている： (1)Ｋｕｎｇ Ｈ．Ｔ．，「何故シストリックアーキテ
クチャなのか？」、COMPUTER，１５，１，１９８２年１
月、 (2)whitehousＨ．Ｊ．とSpeiserＪ．Ｍ．，「シストリ
ックアレイ技術のソナーへの応用」、ＩＥＥＥ ＥＡＳ
ＣＯＮ，ワシントン特別区，１９８１年１１月、 (3)MeadＣ．Ａ．とConwayＬ．Ａ．，「ＶＬＳＩシステ
ム概論」、Addison-Wesley，リーディング，マサチュー
セッツ州，１９８０年。
の研究は、今後のソナープロセッサがシストリック（sy
stolic）アーキテクチャを採用することになろうと指摘
している。これによるとソフトウエアは、各エレメント
が最も隣接のものとのみ接続されたシストリック処理エ
レメント（ＳＰＥ）の多次元的なＶＬＳＩアレイ上で実
行される。このようなアーキテクチャに関する説明は、
その応用や性能と共に、下記を含め多くの筆者によって
成されている： (1)Ｋｕｎｇ Ｈ．Ｔ．，「何故シストリックアーキテ
クチャなのか？」、COMPUTER，１５，１，１９８２年１
月、 (2)whitehousＨ．Ｊ．とSpeiserＪ．Ｍ．，「シストリ
ックアレイ技術のソナーへの応用」、ＩＥＥＥ ＥＡＳ
ＣＯＮ，ワシントン特別区，１９８１年１１月、 (3)MeadＣ．Ａ．とConwayＬ．Ａ．，「ＶＬＳＩシステ
ム概論」、Addison-Wesley，リーディング，マサチュー
セッツ州，１９８０年。
(4)SnyderＬ．，「再構成可能な高並列コンピユータ概
論」、ＣＯＭＰＵＴＥＲ，１５，１，１９８２年１月、
及び (5)BertramＪ．Ｆ．，FamseyerＲ．Ｒ．とHeinsＪ．
Ｍ．，「第５世代のデジタルソナー信号処理」、ＩＥＥ
Ｅ Journal of Oceanic Engineering，１９７７年１０
月。
論」、ＣＯＭＰＵＴＥＲ，１５，１，１９８２年１月、
及び (5)BertramＪ．Ｆ．，FamseyerＲ．Ｒ．とHeinsＪ．
Ｍ．，「第５世代のデジタルソナー信号処理」、ＩＥＥ
Ｅ Journal of Oceanic Engineering，１９７７年１０
月。
ソナーの信号処理問題に対する上記手法の利点を考える
場合には、システムの信頼性が持つ意味を考慮する必要
がある。SnyderＬ．の「再構成可能な高並列コンピユー
タ概論」に指摘されているように、再構成可能なシスト
リックアレイプロセッサ（ＳＡＰ）の実行は故障に強い
アーキテクチャをもたらす。
場合には、システムの信頼性が持つ意味を考慮する必要
がある。SnyderＬ．の「再構成可能な高並列コンピユー
タ概論」に指摘されているように、再構成可能なシスト
リックアレイプロセッサ（ＳＡＰ）の実行は故障に強い
アーキテクチャをもたらす。
この出願は、実際の使用環境下でプロセッサが限定され
た自己補修特性を持ち、１個以上のエレメントの故障時
にオペレータの介入やシステムの停止を必要としないよ
うな特殊のシストリック構成可能アレイプロセッサ（Ｓ
ＣＡＰ）を意図したものである。システムの耐故障性に
関する試験的な解析も得られている。それほど重要でな
い用途では、こうしたアーキテクチャがＶＬＳＩ素子の
製造における歩どまり率を有効に上昇し得ることが認め
られている。
た自己補修特性を持ち、１個以上のエレメントの故障時
にオペレータの介入やシステムの停止を必要としないよ
うな特殊のシストリック構成可能アレイプロセッサ（Ｓ
ＣＡＰ）を意図したものである。システムの耐故障性に
関する試験的な解析も得られている。それほど重要でな
い用途では、こうしたアーキテクチャがＶＬＳＩ素子の
製造における歩どまり率を有効に上昇し得ることが認め
られている。
発明 この発明のシステムは一般に、相互に直交する列状に配
列された一連のエレメントを有するモジュールから成
り、処理されるべきデータは通常垂直及び水平の列を辿
るが、動作中の１つ又は複数のエレメントが万一破損す
ると、次の列中の利用可能なエレメントへの２次路が形
成されこゝからチップを通る最初のエレメントの列へ戻
って辿るように、各エレメント間の連続路がバイアスさ
れる。
列された一連のエレメントを有するモジュールから成
り、処理されるべきデータは通常垂直及び水平の列を辿
るが、動作中の１つ又は複数のエレメントが万一破損す
ると、次の列中の利用可能なエレメントへの２次路が形
成されこゝからチップを通る最初のエレメントの列へ戻
って辿るように、各エレメント間の連続路がバイアスさ
れる。
この発明の方法は、相互に直交する列状に配置され、且
つ処理されるデータが通常垂直及び水平の各列を辿って
所定の経路形状を維持するようにバイアスされた各エレ
メント間の連続路を有する一連のシストリック処理エレ
メント（ＳＰＥ）を用い、各ＳＰＥの機能性を確立する
段階と、ある列のデータ路を次の列中の近いＳＰＥへ向
けることにより正しく機能しないＳＰＥをバイパスする
段階と、データ路を上記次のＳＰＥから最初の列へ戻し
最初の経路形状を維持する段階とから成ることを特徴と
する。
つ処理されるデータが通常垂直及び水平の各列を辿って
所定の経路形状を維持するようにバイアスされた各エレ
メント間の連続路を有する一連のシストリック処理エレ
メント（ＳＰＥ）を用い、各ＳＰＥの機能性を確立する
段階と、ある列のデータ路を次の列中の近いＳＰＥへ向
けることにより正しく機能しないＳＰＥをバイパスする
段階と、データ路を上記次のＳＰＥから最初の列へ戻し
最初の経路形状を維持する段階とから成ることを特徴と
する。
プロセッサは、一連のシストリック処理エレメント（Ｓ
ＰＥ）が相互に直交する列状に配置され、且つ処理され
るデータが通常垂直及び水平の各列を辿って所定の経路
形状を維持するようにバイアスされた各エレメント間の
連続路を有するようなＬＳＩ又はＶＬＳＩから成り、所
定列中の正しく機能しないＳＰＥを検知する手段と、非
機能ＳＰＥに隣接した次の列中の正常機能ＳＰＥへデー
タ路をそらせることによって非機能ＳＰＥを避けてデー
タ路を迂回させ、次いで所定列中の次のＳＰＥへ戻して
最初の経路形状を維持する手段とを備えることを特徴と
している。
ＰＥ）が相互に直交する列状に配置され、且つ処理され
るデータが通常垂直及び水平の各列を辿って所定の経路
形状を維持するようにバイアスされた各エレメント間の
連続路を有するようなＬＳＩ又はＶＬＳＩから成り、所
定列中の正しく機能しないＳＰＥを検知する手段と、非
機能ＳＰＥに隣接した次の列中の正常機能ＳＰＥへデー
タ路をそらせることによって非機能ＳＰＥを避けてデー
タ路を迂回させ、次いで所定列中の次のＳＰＥへ戻して
最初の経路形状を維持する手段とを備えることを特徴と
している。
図面 第１図はエレメントの列中２個のエレメントが作動不能
で、変更されたフロー路が示されているモジュールを表
わした概略図， 第２図は基本のソナーシステムを示す、 第３図は内積の累積エレメントを示す、 第４図はマトリックス−マトリックスの乗算の仕組みを
示す。
で、変更されたフロー路が示されているモジュールを表
わした概略図， 第２図は基本のソナーシステムを示す、 第３図は内積の累積エレメントを示す、 第４図はマトリックス−マトリックスの乗算の仕組みを
示す。
第５図はｐｑ番目のＳＰＥに対応したプロセッサ，優先
順位及び列データ路を示すテーブル， 第６図はスピードと信頼性を向上させるための分割され
たシストリックアレイを示すもので； 第６図(a)図は（Ｎ＋１）×Ｎアレイを示し， 第６図(b)図は（Ｎ＋２）×Ｎアレイを示し， 第６図(c)図は別の（Ｎ＋２）×Ｎアレイを示す， 第７図は２次元の冗長度を備えたアレイを示す， 第８図は３２×３２エレメントアレイに関するシステム
信頼性のグラフ比較を示すもので、実線のグラフは冗長
度なしの状態、鎖線は第６図(a)図の構造の信頼性、点
線は第６図(b)及び(c)図の構造の信頼性をそれぞれ示
す， 第９図は第１図に対応した図だが、２次元的な冗長を示
す、 第１０図はデータ路の詳細な切換えと制御を含むシスト
リック処理エレメントを示す， 第１１図はシストリック処理エレメント間の制御とデー
タ路の相互接続を示す， 第１２図は“棒線（stick）”表示で、ゲートロジック
を最小限とするために“考慮せず（don′t cares）”が
与えられているマルチプレクサのＮＭＯＳ ＶＬＳＩ実
行を示す。
順位及び列データ路を示すテーブル， 第６図はスピードと信頼性を向上させるための分割され
たシストリックアレイを示すもので； 第６図(a)図は（Ｎ＋１）×Ｎアレイを示し， 第６図(b)図は（Ｎ＋２）×Ｎアレイを示し， 第６図(c)図は別の（Ｎ＋２）×Ｎアレイを示す， 第７図は２次元の冗長度を備えたアレイを示す， 第８図は３２×３２エレメントアレイに関するシステム
信頼性のグラフ比較を示すもので、実線のグラフは冗長
度なしの状態、鎖線は第６図(a)図の構造の信頼性、点
線は第６図(b)及び(c)図の構造の信頼性をそれぞれ示
す， 第９図は第１図に対応した図だが、２次元的な冗長を示
す、 第１０図はデータ路の詳細な切換えと制御を含むシスト
リック処理エレメントを示す， 第１１図はシストリック処理エレメント間の制御とデー
タ路の相互接続を示す， 第１２図は“棒線（stick）”表示で、ゲートロジック
を最小限とするために“考慮せず（don′t cares）”が
与えられているマルチプレクサのＮＭＯＳ ＶＬＳＩ実
行を示す。
図面中まず第１図を参照すると、それぞれ列の交差点に
シストリック処理エレメントＳＰＥを備えた水平列Ｈと
垂直列Ｖが示してあり、これらの列は２個の機能しない
エレメントＳＰＥ１とＳＰＥ２を含む。同図には更に路
のバイアスを通じアルゴリズムによって確立されたフロ
ー路が示されており、路へ供給される信号は、特定列中
の動作不能又は動作中のエレメントを検知し、次いで次
の動作可能エレメントへ迂回して、路のターミナル順序
を乱さずに再び元の列へ戻すテスト信号を含む。しかし
ながら、もしＳＰＥ１とＳＰＥ２が完全に機能している
とするならば、最下位列の全てのＳＰＥは、機能維持の
ために予備的に存在が要求されるという意味において以
外は、冗長である。即ち、より下方のＳＰＥは、故障が
発生しないアレイにおいては冗長とされる。ＳＰＥが故
障した場合にＳＰＥの機能を引き継ぐよう、少なくとも
１つの底部列のエレメントが存在しなければならない。
最初のＳＰＥが故障した後、底部列のＳＰＥの１つが故
障したＳＰＥの論理位置を引き継ぐよう使用され、この
結果、冗長なＳＰＥは１つ減少するであろう。
シストリック処理エレメントＳＰＥを備えた水平列Ｈと
垂直列Ｖが示してあり、これらの列は２個の機能しない
エレメントＳＰＥ１とＳＰＥ２を含む。同図には更に路
のバイアスを通じアルゴリズムによって確立されたフロ
ー路が示されており、路へ供給される信号は、特定列中
の動作不能又は動作中のエレメントを検知し、次いで次
の動作可能エレメントへ迂回して、路のターミナル順序
を乱さずに再び元の列へ戻すテスト信号を含む。しかし
ながら、もしＳＰＥ１とＳＰＥ２が完全に機能している
とするならば、最下位列の全てのＳＰＥは、機能維持の
ために予備的に存在が要求されるという意味において以
外は、冗長である。即ち、より下方のＳＰＥは、故障が
発生しないアレイにおいては冗長とされる。ＳＰＥが故
障した場合にＳＰＥの機能を引き継ぐよう、少なくとも
１つの底部列のエレメントが存在しなければならない。
最初のＳＰＥが故障した後、底部列のＳＰＥの１つが故
障したＳＰＥの論理位置を引き継ぐよう使用され、この
結果、冗長なＳＰＥは１つ減少するであろう。
このようなシステムでは多数エレメントが存在し得るか
ら、これまでチップ又はエレメントの交換が必要だった
のに対し、本発明では処理手順に利用可能な代替エレメ
ントを用いてチップの機能を続行させることができる。
ら、これまでチップ又はエレメントの交換が必要だった
のに対し、本発明では処理手順に利用可能な代替エレメ
ントを用いてチップの機能を続行させることができる。
ソナー信号処理システム 第２図に概略的に示した基本のソナーシステムについて
次に見る。
次に見る。
このシステムで演算的に集中した構成要素は、ビーム形
成機である。フーリエ係数のＮ×ＮマトリックスＦを次
式で表わすとする： ｆpq＝ｅｘｐ（−i2πpq／Ｎ）(1) 横列順のＮ個のセンサアレイサンプルがＮ×Ｎのマトリ
ックスＡを限定するとすれば、ＦＡはそれらの縦列が各
センサ出力の離散フーリエ変換（ＤＦＴ）であるマトリ
ックスを成す。次に、マトリックスＦＡＦはＡの２次元
的なＤＦＴで、ビーム形成機能を果す。従ってビーム形
成機は、全体のマトリックス乗算を実行するアーキテク
チャによって実行し得る。
成機である。フーリエ係数のＮ×ＮマトリックスＦを次
式で表わすとする： ｆpq＝ｅｘｐ（−i2πpq／Ｎ）(1) 横列順のＮ個のセンサアレイサンプルがＮ×Ｎのマトリ
ックスＡを限定するとすれば、ＦＡはそれらの縦列が各
センサ出力の離散フーリエ変換（ＤＦＴ）であるマトリ
ックスを成す。次に、マトリックスＦＡＦはＡの２次元
的なＤＦＴで、ビーム形成機能を果す。従ってビーム形
成機は、全体のマトリックス乗算を実行するアーキテク
チャによって実行し得る。
実行 前述したWhitehouseとSpeiserは、第３図に示すような
所定の内積の累算を実施するエレメントから成るＳＡＰ
について述べている。
所定の内積の累算を実施するエレメントから成るＳＡＰ
について述べている。
このプロセッサで実行されるマトリックス−マトリック
ス乗算のデータフローを第４図に示す。演算は３Ｎ−２
サイクルで行われ、パイプライン制御がほゞ完全な利用
を達成し得る。
ス乗算のデータフローを第４図に示す。演算は３Ｎ−２
サイクルで行われ、パイプライン制御がほゞ完全な利用
を達成し得る。
シストリック構成可能プロセッサ 上記のようなプロセッサ内でいずれかの処理エレメント
が故障すると、システム全体の故障をもたらす。しか
し、ＳＰＥの冗長によって信頼性を得られるようにする
構造を考えることができる。シストリックアーキテクチ
ャは、プロセッサ間のデータ路を用いて定義できる。つ
まりこのアーキテクチャにおいて、 ｛ｄijｄi+1,j：ｉ＝１，・・・，Ｎ−１：ｊ＝１，・
・・，Ｎ｝ が垂直路を限定し、 ｛ｄijｄi,j+1：ｉ＝１，・・・，Ｎ：ｊ＝１，・・
・，Ｎ−１｝ が水平路を限定する。入出力両データ転送用の任意路に
ついて、独立のバスを実行し得る。
が故障すると、システム全体の故障をもたらす。しか
し、ＳＰＥの冗長によって信頼性を得られるようにする
構造を考えることができる。シストリックアーキテクチ
ャは、プロセッサ間のデータ路を用いて定義できる。つ
まりこのアーキテクチャにおいて、 ｛ｄijｄi+1,j：ｉ＝１，・・・，Ｎ−１：ｊ＝１，・
・・，Ｎ｝ が垂直路を限定し、 ｛ｄijｄi,j+1：ｉ＝１，・・・，Ｎ：ｊ＝１，・・
・，Ｎ−１｝ が水平路を限定する。入出力両データ転送用の任意路に
ついて、独立のバスを実行し得る。
冗長度に関して、この基本構造は付加的なｋ列のＳＰＥ
を付加することによって拡張され得る。ここで、付加的
な垂直路は、 ｛ｄijｄi+1,j：ｉ＝Ｎ，・・・，Ｎ＋ｋ−１：ｊ＝
１，・・・，Ｎ｝ によって定義され、 付加的な水平路は、 ｛ｄijｄi,j+1：ｉ＝Ｎ＋１，・・・，Ｎ＋ｋ：ｊ＝
１，・・・，Ｎ−１｝ によって定義される。この結果、対角経路は、 ｛ｄijｄi+r,j+1：ｉ＝１，・・・，Ｎ＋ｋ−ｒ：ｊ＝
１，・・・，Ｎ−１：ｒ＝１，・・・，ｋ｝ ｛ｄijｄi-r,j+1：ｉ＝ｒ＋１，・・・，Ｎ＋ｋ：ｊ＝
１，・・・，Ｎ−１：ｒ＝１，・・・，ｋ｝ によって定義され、バイパス経路は、 ｛ｄijｄi+2,j：ｉ＝１，・・・，Ｎ＋ｋ−２：ｊ＝
１，・・・，Ｎ｝ によって定義される。
を付加することによって拡張され得る。ここで、付加的
な垂直路は、 ｛ｄijｄi+1,j：ｉ＝Ｎ，・・・，Ｎ＋ｋ−１：ｊ＝
１，・・・，Ｎ｝ によって定義され、 付加的な水平路は、 ｛ｄijｄi,j+1：ｉ＝Ｎ＋１，・・・，Ｎ＋ｋ：ｊ＝
１，・・・，Ｎ−１｝ によって定義される。この結果、対角経路は、 ｛ｄijｄi+r,j+1：ｉ＝１，・・・，Ｎ＋ｋ−ｒ：ｊ＝
１，・・・，Ｎ−１：ｒ＝１，・・・，ｋ｝ ｛ｄijｄi-r,j+1：ｉ＝ｒ＋１，・・・，Ｎ＋ｋ：ｊ＝
１，・・・，Ｎ−１：ｒ＝１，・・・，ｋ｝ によって定義され、バイパス経路は、 ｛ｄijｄi+2,j：ｉ＝１，・・・，Ｎ＋ｋ−２：ｊ＝
１，・・・，Ｎ｝ によって定義される。
路dij di＋２，j：ｉ＝１，…，（Ｎ−２）：ｊ＝ｉ，
…，Ｎは、明確にするためにのみ定義されている。これ
ら路は、論理的路であり、これらは、路dij di＋１，ｊ
を路di＋１，ｊ di＋２，ｊに接続することにより、各
ｉ，ｊに対して構成されるので、付加的な物理的路を必
要としない。故障の検知とデータ路の再構成プロセスが
完全に成されるまでに、各列のｋ個のＳＰＥまでの故障
はシステムのエラーを生ずるだけである。故障したＳＰ
Ｅは最初の経路形状を保つようにバイパスされ、処理量
の低下は生じない。実施上の困難さが、このようにして
含まれるべき冗長エレメントの最大数を制限する。ｋが
増加するにつれ、データ路に関連する回路の複雑さが増
し、ＳＰＥの回路の複雑さを越えてしまう。従って、デ
ータ路の信頼性がＳＰＥの信頼性よりはるかに高いこと
を保証するため、こゝでは可能な最小冗長度１での実行
について考える。システムの正しい動作には、各ＳＰＥ
がデータと結果を正しく機能する隣りのＳＰＥへ伝えら
れるようにするデータ路の選択手順を定める必要があ
る。ＳＰＥの機能性が各エレメント自身によってフラグ
表示されることは後に示す。
…，Ｎは、明確にするためにのみ定義されている。これ
ら路は、論理的路であり、これらは、路dij di＋１，ｊ
を路di＋１，ｊ di＋２，ｊに接続することにより、各
ｉ，ｊに対して構成されるので、付加的な物理的路を必
要としない。故障の検知とデータ路の再構成プロセスが
完全に成されるまでに、各列のｋ個のＳＰＥまでの故障
はシステムのエラーを生ずるだけである。故障したＳＰ
Ｅは最初の経路形状を保つようにバイパスされ、処理量
の低下は生じない。実施上の困難さが、このようにして
含まれるべき冗長エレメントの最大数を制限する。ｋが
増加するにつれ、データ路に関連する回路の複雑さが増
し、ＳＰＥの回路の複雑さを越えてしまう。従って、デ
ータ路の信頼性がＳＰＥの信頼性よりはるかに高いこと
を保証するため、こゝでは可能な最小冗長度１での実行
について考える。システムの正しい動作には、各ＳＰＥ
がデータと結果を正しく機能する隣りのＳＰＥへ伝えら
れるようにするデータ路の選択手順を定める必要があ
る。ＳＰＥの機能性が各エレメント自身によってフラグ
表示されることは後に示す。
ｐｑ番目のＳＰＥについて可能な列データ路が、第５図
のテーブルに詳しく示してある。これは単一の冗長ＳＰ
Ｅ列を有する自己補修形システムについての経路を示し
たものである。図から明かなように、３つの可能な入力
経路だけがＳＰＥの入力及びＳＰＥの出力に利用でき
る。これら３つの入力経路及び出力経路は、第５図のテ
ーブルの３つの列によって示されている。１つ以上のＳ
ＰＥの冗長列を有するアレイに関し、テーブルは、例え
ば２個の冗長列に関しては、そのテーブルサイズを５列
に増加させる。簡単のため、ＳＰＥの冗長列が１つのみ
の場合を以下に示す。
のテーブルに詳しく示してある。これは単一の冗長ＳＰ
Ｅ列を有する自己補修形システムについての経路を示し
たものである。図から明かなように、３つの可能な入力
経路だけがＳＰＥの入力及びＳＰＥの出力に利用でき
る。これら３つの入力経路及び出力経路は、第５図のテ
ーブルの３つの列によって示されている。１つ以上のＳ
ＰＥの冗長列を有するアレイに関し、テーブルは、例え
ば２個の冗長列に関しては、そのテーブルサイズを５列
に増加させる。簡単のため、ＳＰＥの冗長列が１つのみ
の場合を以下に示す。
第５図を参照すれば明かなように、入力データ路は、最
高優先順位を要求するプロセッサからの作動要求に対し
確認を送出するｐｑ番目のＳＰＥと、残り２つのプロセ
ッサに対する“ふさがり”信号とによって決まる。入力
データ路は、最低優先順位を持つ出力プロセッサに向か
うものである。例えば、第１図の上部列の中間のＳＰＥ
を考えてみる。このアレイの外を定義するようなデータ
路が存在しない場合、このＳＰＥは第５図の底の２列に
関連する。故障が存在しないアレイを考えた場合、この
ＳＰＥに対する入力は左側の最初のＳＰＥである。更
に、このＳＰＥの出力は右側の最初のＳＰＥである。要
求を出すプロセッサの優先順位と共にふさがり信号はア
レイの正確な機能を確実なものとし、全体的に故障が存
在しない状態では、データ路は通常の格子を形成するこ
とに注意すべきである。
高優先順位を要求するプロセッサからの作動要求に対し
確認を送出するｐｑ番目のＳＰＥと、残り２つのプロセ
ッサに対する“ふさがり”信号とによって決まる。入力
データ路は、最低優先順位を持つ出力プロセッサに向か
うものである。例えば、第１図の上部列の中間のＳＰＥ
を考えてみる。このアレイの外を定義するようなデータ
路が存在しない場合、このＳＰＥは第５図の底の２列に
関連する。故障が存在しないアレイを考えた場合、この
ＳＰＥに対する入力は左側の最初のＳＰＥである。更
に、このＳＰＥの出力は右側の最初のＳＰＥである。要
求を出すプロセッサの優先順位と共にふさがり信号はア
レイの正確な機能を確実なものとし、全体的に故障が存
在しない状態では、データ路は通常の格子を形成するこ
とに注意すべきである。
ＶＬＳＩの実施では、全てのエレメントを同一視し得る
ことも可能であるため、ＳＰＥアレイからのデータ路
は、アレイの境界外部のＳＰＥに向けることが可能であ
る。この結果、エッジアレイＳＰＥやエッジアレイＳＰ
Ｅ付近からのデータ路はアレイから出て、ハードウエア
的に初期化され「ふさがり」信号を戻す。これらの路が
正しい初期構造を形成する。ｐｑ番目のＳＰＥが故障す
ると、“ふさがり”信号が全ての入力プロセッサに戻さ
れる。そして、データ路ｄp-1,qｄp+1,qが付勢されて縦
列エレメントをバイパスする。
ことも可能であるため、ＳＰＥアレイからのデータ路
は、アレイの境界外部のＳＰＥに向けることが可能であ
る。この結果、エッジアレイＳＰＥやエッジアレイＳＰ
Ｅ付近からのデータ路はアレイから出て、ハードウエア
的に初期化され「ふさがり」信号を戻す。これらの路が
正しい初期構造を形成する。ｐｑ番目のＳＰＥが故障す
ると、“ふさがり”信号が全ての入力プロセッサに戻さ
れる。そして、データ路ｄp-1,qｄp+1,qが付勢されて縦
列エレメントをバイパスする。
ＳＰＥ故障のためｐｑ番目のエレメントが利用できる出
力データ路が存在しないと、そのエレメントも“故障”
する。つまりシステムの故障状態となり、これがアレイ
のエッジに戻され、スーパバイザに報告される。このダ
イナミック構造は故障したＳＰＥをバイパスすると共
に、機能性が回復されたらそのＳＰＥを動作構造に戻す
ことが可能である。システム故障の状態では、機能アレ
イの大きさは減少してしまうが、それでもまだ、アレイ
はその減少した容量を用いてデータを処理することがで
きる。例えば、単一の冗長エレメント（｛ｎ＋１｝×
ｎ）の列を有する（ｎ×ｎ）のプロセッサにおいて、２
つの縦列エレメントが故障している場合を考えてみる。
利用可能なアレイの大きさはたったの（｛ｎ−１｝×
ｎ）であり、これは完全に修復される故障を示している
が、それでもまだ、完全に機能するアレイの（｛ｎ−
１｝／ｎ）、若しくは縦列毎に１つ以上の故障したエレ
メントを有しないような自己修復形アレイと同じだけの
計算能力を与えてくれるのである。
力データ路が存在しないと、そのエレメントも“故障”
する。つまりシステムの故障状態となり、これがアレイ
のエッジに戻され、スーパバイザに報告される。このダ
イナミック構造は故障したＳＰＥをバイパスすると共
に、機能性が回復されたらそのＳＰＥを動作構造に戻す
ことが可能である。システム故障の状態では、機能アレ
イの大きさは減少してしまうが、それでもまだ、アレイ
はその減少した容量を用いてデータを処理することがで
きる。例えば、単一の冗長エレメント（｛ｎ＋１｝×
ｎ）の列を有する（ｎ×ｎ）のプロセッサにおいて、２
つの縦列エレメントが故障している場合を考えてみる。
利用可能なアレイの大きさはたったの（｛ｎ−１｝×
ｎ）であり、これは完全に修復される故障を示している
が、それでもまだ、完全に機能するアレイの（｛ｎ−
１｝／ｎ）、若しくは縦列毎に１つ以上の故障したエレ
メントを有しないような自己修復形アレイと同じだけの
計算能力を与えてくれるのである。
ＳＣＡＰにおける故障検知 モジュラー形ソナー信号プロセッサにおけるオンライン
性能のモニター，故障の検出と位置決めの実施方法は、
前出のBartram，Ｊ．Ｆ。，Ramseyer Ｒ．Ｒ。と Heines Ｊ。Ｍ。によって簡単に論じられている。各モ
ジュールの機能性を制御するスーパーバイザエレメント
は同時に、モジュールについての定期的な診断アルゴリ
ズムを実行し、システムの制御装置に報告する。小区画
化アレイのＳＰＥについても、同様の診断手法が考えら
れる。
性能のモニター，故障の検出と位置決めの実施方法は、
前出のBartram，Ｊ．Ｆ。，Ramseyer Ｒ．Ｒ。と Heines Ｊ。Ｍ。によって簡単に論じられている。各モ
ジュールの機能性を制御するスーパーバイザエレメント
は同時に、モジュールについての定期的な診断アルゴリ
ズムを実行し、システムの制御装置に報告する。小区画
化アレイのＳＰＥについても、同様の診断手法が考えら
れる。
標準値と内積累算との比較結果をフラグ表示する診断モ
ードを含めて各ＳＰＥが設計されていれば、各アレイエ
レメントの機能性をテストできる。マトリックスの積， ＡＢ＝Ｃ (2) 但しaij＝０，ｊ＞２及びbij＝０，ｉ＞２，は２つのパ
イプライン式サイクルで完全である。得られたマトリッ
クスの累算内積の項は、それが正しければ、データ路と
ＳＰＥ両方が正しく機能していることを実証する。診断
モードビットが１次元で各データ路に加えられると、完
全な診断アルゴリズムがシストリック的にアレイを通過
可能となる。それぞれ完全なマトリックス乗算後に実施
されると、性能は（２／Ｎ）×１００％だけ低下する。
使用マトリックスを増せば、冗長エレメントもテスト可
能となる。次いで、いずれかのＳＰＥの故障が、データ
を受入れる冗長エレメント列の故障によってスーパバイ
ザへ通知される。つまり、２列の故障がシステムの故障
を表わす。
ードを含めて各ＳＰＥが設計されていれば、各アレイエ
レメントの機能性をテストできる。マトリックスの積， ＡＢ＝Ｃ (2) 但しaij＝０，ｊ＞２及びbij＝０，ｉ＞２，は２つのパ
イプライン式サイクルで完全である。得られたマトリッ
クスの累算内積の項は、それが正しければ、データ路と
ＳＰＥ両方が正しく機能していることを実証する。診断
モードビットが１次元で各データ路に加えられると、完
全な診断アルゴリズムがシストリック的にアレイを通過
可能となる。それぞれ完全なマトリックス乗算後に実施
されると、性能は（２／Ｎ）×１００％だけ低下する。
使用マトリックスを増せば、冗長エレメントもテスト可
能となる。次いで、いずれかのＳＰＥの故障が、データ
を受入れる冗長エレメント列の故障によってスーパバイ
ザへ通知される。つまり、２列の故障がシステムの故障
を表わす。
信頼性の解析 ｍ×ｎアレイ（但しｍ＞ｎ）のＳＰＥを考えることにす
る。作動エレメントは当初、ｍ−ｎ列の“ホット”スペ
アを備えたｎ×ｎマトリックスを形成する。エレメント
は全て独立していると仮定する。各エレメントの故障時
間ｔｆは、指数関数的分布として与えられる。つまり、 ｆ(tf)＝λexp（−λtf） (3) が故障時間密度の分布で、 Ｆ(tf)＝１−exp（−λtf） (4) が故障時間分布関数である。但しtf＞０。
る。作動エレメントは当初、ｍ−ｎ列の“ホット”スペ
アを備えたｎ×ｎマトリックスを形成する。エレメント
は全て独立していると仮定する。各エレメントの故障時
間ｔｆは、指数関数的分布として与えられる。つまり、 ｆ(tf)＝λexp（−λtf） (3) が故障時間密度の分布で、 Ｆ(tf)＝１−exp（−λtf） (4) が故障時間分布関数である。但しtf＞０。
エレメントが時刻ｔで機能している可能性が、信頼性ｒ
(t)として定義される： すなわちｒ(t)＝Ｐ〔tf＞ｔ〕 ＝１−Ｆ(t) ＝exp（−λt） (5) システム中ｎ−１個のエレメントのみが作動可能のと
き、縦列が故障し、ひいてはシステムを故障させる。ｎ
個のエレメントが正確に時刻ｔでｍ×１の縦列内に残っ
ている可能性は２項的に分布し、次式で与えられる： Ｐｎ(t)＝▲〔m n〕▲ｒ(t)ｕ（１−ｒ(t)）ｍ−ｎ
(6) 独立した残りｎ個のエレメントのうち１個が時間間隔
（ｔ，ｔ＋dt）の間に故障する可能性は： Ｐ１(dt)＝ｎλｄｔ (7) 従って、この時間間隔内に縦列故障が生じる可能性は、 Ｐｆ＝Ｐｎ(t)Ｐ１(dt) (8) ＝▲〔m n〕▲ｒ(t)ｕ（１−ｒ(t)）ｍ−ｎｎλ
dt で、縦列の故障密度関数は次式で与えられる： これをｒ(t)の関数として表わせば、 ｐ(r)＝ｎ▲〔m n〕▲ｒｎ−１(1-r)m-n (10) 縦列が時刻ｔで故障しない確率はその信頼性であり、す
なわち、 これにａ＝ｎ，ｂ−１＝ｍ−ｎを代入すると、 Luke(7)，８、２、３の等式(1)，(3)を使えば、 こゝで2F1（．，．；．；．）は通常のガウス超幾何関
数である。１エレメントという最小冗長度の場合、 Ｒｎ(t)＝(n+1)ｒｎ(1-r)２ 2F1(1,n+2;n+1;r) (1
4) 従ってｎ個の縦列の信頼性つまりシステムの信頼性は、 ▲Ｒn n(t)▲＝（Ｒｎ(t)）ｎ (15) 信頼性向上の構造 式(15)で定義されたシステムの信頼性は改善できる。縦
列当り１個の冗長エレメントという制限の下で、システ
ムの冗長度を向上し得るようにタスクを分解する方法を
次に検討する。
(t)として定義される： すなわちｒ(t)＝Ｐ〔tf＞ｔ〕 ＝１−Ｆ(t) ＝exp（−λt） (5) システム中ｎ−１個のエレメントのみが作動可能のと
き、縦列が故障し、ひいてはシステムを故障させる。ｎ
個のエレメントが正確に時刻ｔでｍ×１の縦列内に残っ
ている可能性は２項的に分布し、次式で与えられる： Ｐｎ(t)＝▲〔m n〕▲ｒ(t)ｕ（１−ｒ(t)）ｍ−ｎ
(6) 独立した残りｎ個のエレメントのうち１個が時間間隔
（ｔ，ｔ＋dt）の間に故障する可能性は： Ｐ１(dt)＝ｎλｄｔ (7) 従って、この時間間隔内に縦列故障が生じる可能性は、 Ｐｆ＝Ｐｎ(t)Ｐ１(dt) (8) ＝▲〔m n〕▲ｒ(t)ｕ（１−ｒ(t)）ｍ−ｎｎλ
dt で、縦列の故障密度関数は次式で与えられる： これをｒ(t)の関数として表わせば、 ｐ(r)＝ｎ▲〔m n〕▲ｒｎ−１(1-r)m-n (10) 縦列が時刻ｔで故障しない確率はその信頼性であり、す
なわち、 これにａ＝ｎ，ｂ−１＝ｍ−ｎを代入すると、 Luke(7)，８、２、３の等式(1)，(3)を使えば、 こゝで2F1（．，．；．；．）は通常のガウス超幾何関
数である。１エレメントという最小冗長度の場合、 Ｒｎ(t)＝(n+1)ｒｎ(1-r)２ 2F1(1,n+2;n+1;r) (1
4) 従ってｎ個の縦列の信頼性つまりシステムの信頼性は、 ▲Ｒn n(t)▲＝（Ｒｎ(t)）ｎ (15) 信頼性向上の構造 式(15)で定義されたシステムの信頼性は改善できる。縦
列当り１個の冗長エレメントという制限の下で、システ
ムの冗長度を向上し得るようにタスクを分解する方法を
次に検討する。
偶数次ｎの２個のマトリックスの積について考えると、
この条件を満すようにゼロで奇数次のマトリックスを増
加できるので、偶数次に限定しても一般性は何ら失われ
ない。第６図(a)図は、縦列当り１個の冗長エレメント
を含む区画アレイに関する乗算の実行を示している。こ
の構造に必要な非パイプライン式実行時間は３ｎ−２サ
イクルである。
この条件を満すようにゼロで奇数次のマトリックスを増
加できるので、偶数次に限定しても一般性は何ら失われ
ない。第６図(a)図は、縦列当り１個の冗長エレメント
を含む区画アレイに関する乗算の実行を示している。こ
の構造に必要な非パイプライン式実行時間は３ｎ−２サ
イクルである。
Whitehouseは、Ｊ×ＮとＮ×Ｋのマトリックス積に関連
して、非正方形アレイの非パイプライン式実行時間を求
めている。次元Ｊ×Ｋの区画アレイについての実行時間
は、Ｎ＋Ｊ＋Ｋ−２サイクルである。
して、非正方形アレイの非パイプライン式実行時間を求
めている。次元Ｊ×Ｋの区画アレイについての実行時間
は、Ｎ＋Ｊ＋Ｋ−２サイクルである。
式(2)のマトリックスを区分すると、 〔A〕〔B1B2〕＝〔C1C2〕 (16) 区分された２個のマトリックス積Ｃ１とＣ２は、２個の
Ｎ／２×Ｎ区画アレイについて並列に演算でき、それぞ
れはＮ×Ｎ／２マトリックスによってＮ×Ｎの積を演算
する。従って演算時間は５Ｎ／２−２サイクルに減少
し、第６(a)図のアレイの再構成が冗長ＳＰＥの比率倍
化を可能とするのが明らかである。再構成されたアレイ
を第６(b)に示す。
Ｎ／２×Ｎ区画アレイについて並列に演算でき、それぞ
れはＮ×Ｎ／２マトリックスによってＮ×Ｎの積を演算
する。従って演算時間は５Ｎ／２−２サイクルに減少
し、第６(a)図のアレイの再構成が冗長ＳＰＥの比率倍
化を可能とするのが明らかである。再構成されたアレイ
を第６(b)に示す。
システムの信頼性は次式で与えられる： Ｒｓ(t)＝▲Ｒ2N N/2〕▲(t) (17) 更に区分すれば次のようになる： この区分の実施を第６(c)図に示す。実行時間は更に短
縮され、２Ｎ−２サイクルとなる。冗長度と信頼性は第
６(b)図と等しいが、故障状態を検知する時間が最小限
化される。
縮され、２Ｎ−２サイクルとなる。冗長度と信頼性は第
６(b)図と等しいが、故障状態を検知する時間が最小限
化される。
２次元的冗長 上記では、特定のデータ路アーキテクチャに対し１次元
的な冗長という考えを実施する点について論じてきた。
的な冗長という考えを実施する点について論じてきた。
もし、この実施例におけるデータ路が二方向性でありう
るならば、第７図および第９図に示すように、２つの次
元において冗長性が導入されうる。第９図に示す路は、
冗長列の数が１のときに１次元的な場合に対して定義さ
れる路の組みから構成される。
るならば、第７図および第９図に示すように、２つの次
元において冗長性が導入されうる。第９図に示す路は、
冗長列の数が１のときに１次元的な場合に対して定義さ
れる路の組みから構成される。
冗長列に対して必要とされる路は、常に、二方向性路を
とるエレメントの単一の冗長行を補助しうるが、これら
路は、エレメントの１つより多い冗長行を補助するため
にはエンハンスメントを必要とする。付加的な路は、冗
長列を補助するのに必要とされる路と論理的に等価であ
るので、ここでは説明しない。
とるエレメントの単一の冗長行を補助しうるが、これら
路は、エレメントの１つより多い冗長行を補助するため
にはエンハンスメントを必要とする。付加的な路は、冗
長列を補助するのに必要とされる路と論理的に等価であ
るので、ここでは説明しない。
第９図におけるデータ路構成は、各次元にて同じバイパ
スアルゴリズムを使用することにより導き出されること
は理解されよう。
スアルゴリズムを使用することにより導き出されること
は理解されよう。
２次元冗長性の解析はここでは行わないが、（１８）の
区分により最高比率の冗長度、最大の信頼性、最も速い
非パイプライン式演算時間を持つ構造が得られることに
留意されたい。
区分により最高比率の冗長度、最大の信頼性、最も速い
非パイプライン式演算時間を持つ構造が得られることに
留意されたい。
第９図において、垂直列のアレイ機能に関する限り、４
個の非機能ＳＰＥ，ＳＰＥ３〜ＳＰＥ６，とモジュール
エッジにおける左側ＳＰＥが冗長である。
個の非機能ＳＰＥ，ＳＰＥ３〜ＳＰＥ６，とモジュール
エッジにおける左側ＳＰＥが冗長である。
第８図は、３２×３２エレメントの主アレイに関し第６
(a)，６(b)及び６(c)図に示した実施例の信頼性を、冗
長なしのシステムと比較したものである。性能が劣化せ
ずに動作するこれらアーキテクチャの能力は、今後のＶ
ＬＳＩ素子の製造において重要な意味を持つ。製造上の
欠陥が存在するのを許容するが、それを自己構成可能な
アーキテクチャでユーザに明白とすることによって、製
造コストが最小限化される。
(a)，６(b)及び６(c)図に示した実施例の信頼性を、冗
長なしのシステムと比較したものである。性能が劣化せ
ずに動作するこれらアーキテクチャの能力は、今後のＶ
ＬＳＩ素子の製造において重要な意味を持つ。製造上の
欠陥が存在するのを許容するが、それを自己構成可能な
アーキテクチャでユーザに明白とすることによって、製
造コストが最小限化される。
実施 第１０図はシストリック処理エレメントを示している。
このエレメントはデータラインによって、その直交する
横列及び縦列を介して通される係数に対し乗−累算機能
が実行可能となる。第１１図は、アレイ中の一つの特定
エレメントに関するデータ及び制御路の相互接続を示し
ている。制御信号は一般の場合に必要なものより少いプ
ロトコールを含むが、高密度なＶＬＳＩの実施を可能と
する。
このエレメントはデータラインによって、その直交する
横列及び縦列を介して通される係数に対し乗−累算機能
が実行可能となる。第１１図は、アレイ中の一つの特定
エレメントに関するデータ及び制御路の相互接続を示し
ている。制御信号は一般の場合に必要なものより少いプ
ロトコールを含むが、高密度なＶＬＳＩの実施を可能と
する。
データ路と制御信号の初期化は、全エレメントの状態を
“故障”にセットするマスターリセットラインによって
行われる。この状態で、各エレメントがＡ１データ入力
からデータを受取る。次いで入力データに付属した命令
によってテースモードが開始され、エレメントの機能性
を定めて“故障”フラグを立てる。全ての制御信号はテ
スト状態の完了時にのみ更新され、隣接するエレメント
にだけ伝えられる。次の動作で使われる正常機能のデー
タ路は、テストモードがアレイ中を縦横に伝播すること
によって確立される。入力データ路の選択は、組合せロ
ジックで制御されるマルチプレクサによって行われる。
組合せロジック回路への入力は、当エレメントの真上及
び右側エレメントの状態出力から直接的に得られる。リ
セット状態を無視すれば、入力データ路マルチプレクサ
用の真理値表は次の通りとなる； 但しＸは“考慮せず（don′t care）”を示す。
“故障”にセットするマスターリセットラインによって
行われる。この状態で、各エレメントがＡ１データ入力
からデータを受取る。次いで入力データに付属した命令
によってテースモードが開始され、エレメントの機能性
を定めて“故障”フラグを立てる。全ての制御信号はテ
スト状態の完了時にのみ更新され、隣接するエレメント
にだけ伝えられる。次の動作で使われる正常機能のデー
タ路は、テストモードがアレイ中を縦横に伝播すること
によって確立される。入力データ路の選択は、組合せロ
ジックで制御されるマルチプレクサによって行われる。
組合せロジック回路への入力は、当エレメントの真上及
び右側エレメントの状態出力から直接的に得られる。リ
セット状態を無視すれば、入力データ路マルチプレクサ
用の真理値表は次の通りとなる； 但しＸは“考慮せず（don′t care）”を示す。
“システム故障”は、縦列中１個より多いエレメントが
故障したときアレイのエッジえ伝わるフラグである。こ
れは１個だけの冗長エレメントでは解決できない状態
で、システムが故障する。
故障したときアレイのエッジえ伝わるフラグである。こ
れは１個だけの冗長エレメントでは解決できない状態
で、システムが故障する。
テストモードがいったん完了すると、次のテストモード
によってエレメントの故障が検知されるまで、データ路
は安定している。故障が検知されると作動路の再構成が
行われ、システムの機能性を回復する。つまり水平デー
タ路が垂直路中の１個又は複数のエレメントを迂回する
ようにバイアスされ、データが“故障”状態にあるエレ
メントを迂回するようにせしめる。データは依然として
その後の全テストを行う故障エレメントに対し使えるの
で、エレメントの回復が可能である。連続するテストが
“故障”フラグを取除き、データ路を回復させる。実施
におけるこの特徴が、別のエスト時に生じない“ソフ
ト”のエラーからの回復を可能とする。
によってエレメントの故障が検知されるまで、データ路
は安定している。故障が検知されると作動路の再構成が
行われ、システムの機能性を回復する。つまり水平デー
タ路が垂直路中の１個又は複数のエレメントを迂回する
ようにバイアスされ、データが“故障”状態にあるエレ
メントを迂回するようにせしめる。データは依然として
その後の全テストを行う故障エレメントに対し使えるの
で、エレメントの回復が可能である。連続するテストが
“故障”フラグを取除き、データ路を回復させる。実施
におけるこの特徴が、別のエスト時に生じない“ソフ
ト”のエラーからの回復を可能とする。
───────────────────────────────────────────────────── フロントページの続き (51)Int.Cl.5 識別記号 庁内整理番号 ＦＩ 技術表示箇所 Ｈ０１Ｌ 27/10 ４９１ 8728−4Ｍ (72)発明者 クラーク アレン パトリツク オーストラリア国 サウス オーストラリ ア 5081 メデインデイー ガーデンス シヤーボーン ロード 22 (56)参考文献 Ｋｕｒｎ ｅｔ．ａｌ．，“Ｐｒｏｃｅ ｅｄｉｎｇ ｏｆ ｔｈｅ ｓｉｘｔｅｅ ｎｔｈ Ｈａｗａｉｉ Ｉｎｔｅｒｎａｔ ｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｓｙｓｔｅｍ Ｓｃｉｅｎｃｅｓ 1983”，（昭58−１），Ｐ．215−224
Claims (7)
- 【請求項１】大規模集積回路モジュール（ＬＳＩ又はＶ
ＬＳＩ）の自己補修方法であって、 １組のシストリック処理エレメントＳＰＥを互いに直交
する列に配置し、 近くのＳＰＥ間において形態優先順位値を伝達し合うこ
とによって、処理すべきデータのデータ路が通常それら
列をたどるようにバイアスされた連続路をＳＰＥの間に
形成し、 初期的に冗長であるようなＳＰＥの列を設け、 各非機能ＳＰＥがＳＰＥ結果と参照値との比較の結果と
してその非機能ＳＰＥ自身によってフラグ表示されるよ
うにすることにより、１つの列のＳＰＥのうちのどれが
非機能ＳＰＥであるかを確立し、 そのような非機能ＳＰＥからデータ路を、データの迂回
をトリガすることにより、別の列における近くのＳＰＥ
へ向けることでそのような非機能ＳＰＥをバイパスし、
このバイパスによって初期的に冗長であるようなＳＰＥ
の少なくとも１つの使用に影響を与え、 近くのＳＰＥと非機能ＳＰＥの確立との間における形態
優先順位値の伝達に基づいて前記近くのＳＰＥからのデ
ータ路を元の列の方へ戻し、正常機能ＳＰＥ間の所望の
路を確立して維持する ことを特徴とする方法。 - 【請求項２】前記回路は、そのエッジにそうエッジ列を
含み、前記エッジ列にそってデータをそらせ且つそのエ
ッジ列におけるＳＰＥの非機能を指示するためにふさが
り信号がエッジ列のＳＰＥへ入力される請求の範囲第１
項記載の方法。 - 【請求項３】自己補修形大規模集積回路モジュールにお
いて、 互いに直交する列のアレイとして配置された１組のシス
トリック処理エレメントＳＰＥであって、前記近くのＳ
ＰＥ間の形態伝達手段によってそれらＳＰＥの間に連続
路が形成され且つその連続路は、処理すべきデータが通
常それら列をたどり選択された列にそうデータ路を維持
するようにバイアスされているような１組のシストリッ
ク処理エレメントＳＰＥと、 非機能ＳＰＥを置換するための少なくとも１つのＳＰＥ
の冗長列と、 各列の非機能ＳＰＥを検出しそれら非機能ＳＰＥをフラ
グ表示するための手段と、 選択された列における少なくとも１つの非機能ＳＰＥを
検出し、そのデータ路を別の列における正常機能ＳＰＥ
へそらせて且つ前記選択された列における次の機能ＳＰ
Ｅへと戻すようにすることにより、近くのＳＰＥ間の形
態伝達手段に基づいて前記非機能ＳＰＥのまわりにその
データ路を迂回させて、正常機能ＳＰＥの間に所望され
た相互接続路を確立し維持するための再構成手段と を備えることを特徴とする自己補修形大規模集積回路モ
ジュール。 - 【請求項４】ＬＳＩまたはＶＬＳＩの如き自己補修形大
規模集積回路モジュールにおいて、 互いに直交する列のアレイに配置された一連のシストリ
ック処理エレメントＳＰＥと、但し、ＳＰＥ間の経路は
処理すべきデータがそれらの列を通常たどり選択された
経路形状を維持するようにしてバイアスされており、 ＳＰＥの少なくとも１つの臨時列であって、互いに対し
且つその他の列のＳＰＥにそれら臨時のＳＰＥを接続す
る次元的な路を有するＳＰＥの少なくとも１つの臨時列
と、 前記ＳＰＥに結合され、選択された列における非機能Ｓ
ＰＥを検出しその非機能ＳＰＥをフラグ表示するテスト
信号を注入する手段とを備え、 前記各ＳＰＥは、前記非機能ＳＰＥのまわりに別の列の
ＳＰＥを通して前記路を迂回させる手段を含んでおり、
前記路の迂回は、ＳＰＥのバイアスに基づいて、前記非
機能ＳＰＥに隣接した第１の正常機能ＳＰＥからその非
機能ＳＰＥに隣接した第２の正常機能ＳＰＥへと、前記
第１の正常機能ＳＰＥに対して反対の側にて行われ、元
の列の路を維持する ことを特徴とする自己補修形大規模集計回路モジュー
ル。 - 【請求項５】前記一連のシストリック処理エレメント
は、そのエッジにそうエッジ列を含み、ＳＰＥのエッジ
列においてふさがりオペレータ信号を開始させ且つデー
タ路をサイドエッジ列にそって向けるための手段を備え
る請求の範囲第４項記載の自己補修形大規模集積回路モ
ジュール。 - 【請求項６】大規模集積回路モジュールの自己補修方法
であって、 １組のシストリック処理エレメントＳＰＥを互いに直交
する列に配置し、 初期的に冗長であるようなＳＰＥの列を設け、 処理すべきデータが通常それら列をたどるようにバイア
スされた連続路をＳＰＥの間に形成し、 各非機能ＳＰＥがＳＰＥ結果と参照値との比較の結果と
してそのＳＰＥ自身によってフラグ表示されるようにす
ることにより、各列の非機能ＳＰＥを確立し、 データの迂回をトリガすることにより、第１の列の非機
能ＳＰＥがその非機能ＳＰＥからのデータ路を、その非
機能ＳＰＥに隣接した少なくとも次の列における受け取
りＳＰＥへ向けるようにさせるようにしてそのような非
機能ＳＰＥをバイパスし、このバイパスによって初期的
に冗長であるようなＳＰＥの少なくとも１つの使用に影
響を与え、 前記受け取りＳＰＥからのデータ路を前記第１の列のＳ
ＰＥへ戻して、正常機能ＳＰＥがこれにより前記モジュ
ールからの入口路に関連して前記モジュールからの出口
路を確立し且つ可能ならば維持しうるようにする ことを特徴とする方法。 - 【請求項７】自己補修形大規模集積回路モジュール（Ｌ
ＳＩ又はＶＬＳＩ）において、 互いに直交する列に配置された１組のシストリック処理
エレメント、即ち、ＳＰＥと、 各エレメント間の複数のデータ伝送路と、 非機能ＳＰＥを置換するための少なくとも１つのＳＰＥ
の冗長列と、 処理すべきデータが通常それら列をたどるようにデータ
伝送路を選択する手段と、 各ＳＰＥにおいてＳＰＥ結果と参照値との比較の結果と
して各路の非機能ＳＰＥをフラグ表示する手段と を備えており、 前記データ伝送路は、第１の列のそのような非機能ＳＰ
Ｅが、その非機能ＳＰＥからデータ路を向けて、その非
機能ＳＰＥに隣接した少なくとも次の列における受け取
りＳＰＥへのデータの迂回をトリガするようにバイアス
されており、 さらに、前記受け取りＳＰＥからのデータ路を前記第１
の列におけるＳＰＥへ向けて、これにより、正常機能Ｓ
ＰＥが入口路に関して出口路を確立させ且つ可能ならば
維持するようにする手段を備えることを特徴とする自己
補修形大規模集積回路モジュール。
Applications Claiming Priority (3)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| AU8826 | 1983-04-11 | ||
| AUPF882683 | 1983-04-11 | ||
| PCT/AU1984/000053 WO1984004225A1 (en) | 1983-04-11 | 1984-04-09 | Self repair large scale integrated circuit |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS60501032A JPS60501032A (ja) | 1985-07-04 |
| JPH0616270B2 true JPH0616270B2 (ja) | 1994-03-02 |
Family
ID=3770086
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP59501474A Expired - Lifetime JPH0616270B2 (ja) | 1983-04-11 | 1984-04-09 | 自己補修形大規模集積回路 |
Country Status (7)
| Country | Link |
|---|---|
| US (1) | US4698807A (ja) |
| EP (1) | EP0142510B1 (ja) |
| JP (1) | JPH0616270B2 (ja) |
| CA (1) | CA1219965A (ja) |
| DE (1) | DE3483455D1 (ja) |
| NZ (1) | NZ207742A (ja) |
| WO (1) | WO1984004225A1 (ja) |
Families Citing this family (19)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4758999A (en) * | 1984-12-03 | 1988-07-19 | The Commonwealth Of Australia | Systolic architectures for sonar processing |
| DE3681463D1 (de) * | 1985-01-29 | 1991-10-24 | Secr Defence Brit | Verarbeitungszelle fuer fehlertolerante matrixanordnungen. |
| 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 |
| GB8612454D0 (en) * | 1986-05-22 | 1986-07-02 | Inmos Ltd | Redundancy scheme for multi-stage apparatus |
| US4928022A (en) * | 1987-07-17 | 1990-05-22 | Trw Inc. | Redundancy interconnection circuitry |
| US4920497A (en) * | 1987-10-27 | 1990-04-24 | State University Of New York | Method for rendering usuable a defective raw programmable logic array and a defective programmable logic array rendered usable by this method |
| US5020059A (en) * | 1989-03-31 | 1991-05-28 | At&T Bell Laboratories | Reconfigurable signal processor |
| US4962381A (en) * | 1989-04-11 | 1990-10-09 | General Electric Company | Systolic array processing apparatus |
| US5280607A (en) * | 1991-06-28 | 1994-01-18 | International Business Machines Corporation | Method and apparatus for tolerating faults in mesh architectures |
| US5271014A (en) * | 1992-05-04 | 1993-12-14 | International Business Machines Corporation | Method and apparatus for a fault-tolerant mesh with spare nodes |
| US5513313A (en) * | 1993-01-19 | 1996-04-30 | International Business Machines Corporation | Method for generating hierarchical fault-tolerant mesh architectures |
| 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 |
| US6408402B1 (en) | 1994-03-22 | 2002-06-18 | Hyperchip Inc. | Efficient direct replacement cell fault tolerant architecture |
| US6067633A (en) * | 1998-03-31 | 2000-05-23 | International Business Machines Corp | Design and methodology for manufacturing data processing systems having multiple processors |
| US6120449A (en) * | 1998-11-25 | 2000-09-19 | General Electric Company | Method and apparatus for compensating for inoperative elements in ultrasonic transducer array |
| JP3968057B2 (ja) * | 2003-06-18 | 2007-08-29 | 日本電信電話株式会社 | Ｎ＋１冗長構成デバイス切替制御装置 |
| US20100241783A1 (en) * | 2009-03-23 | 2010-09-23 | Honeywell International Inc. | Memory node for use within a data storage system having a plurality of interconnected memory nodes |
| CN105975435A (zh) * | 2016-06-17 | 2016-09-28 | 广东工业大学 | 一种含开关及连线故障的处理器阵列的重构方法 |
| CN109788498A (zh) * | 2018-12-04 | 2019-05-21 | 天津大学 | 传感器网络中基于冗余节点选择调度模型的拓扑修复方法 |
Family Cites Families (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US3665418A (en) * | 1968-07-15 | 1972-05-23 | Ibm | Status switching in an automatically repaired computer |
| US3665173A (en) * | 1968-09-03 | 1972-05-23 | Ibm | Triple modular redundancy/sparing |
| US3654610A (en) * | 1970-09-28 | 1972-04-04 | Fairchild Camera Instr Co | Use of faulty storage circuits by position coding |
| US3805039A (en) * | 1972-11-30 | 1974-04-16 | Raytheon Co | High reliability system employing subelement redundancy |
| US4533993A (en) * | 1981-08-18 | 1985-08-06 | National Research Development Corp. | Multiple processing cell digital data processor |
| US4438494A (en) * | 1981-08-25 | 1984-03-20 | Intel Corporation | Apparatus of fault-handling in a multiprocessing system |
-
1984
- 1984-04-04 CA CA000451241A patent/CA1219965A/en not_active Expired
- 1984-04-04 NZ NZ207742A patent/NZ207742A/xx unknown
- 1984-04-09 EP EP84901307A patent/EP0142510B1/en not_active Expired
- 1984-04-09 US US06/691,191 patent/US4698807A/en not_active Expired - Fee Related
- 1984-04-09 DE DE8484901307T patent/DE3483455D1/de not_active Expired - Lifetime
- 1984-04-09 JP JP59501474A patent/JPH0616270B2/ja not_active Expired - Lifetime
- 1984-04-09 WO PCT/AU1984/000053 patent/WO1984004225A1/en not_active Ceased
Non-Patent Citations (2)
| Title |
|---|
| Ｋｕｒｎｅｔ．ａｌ．，"ＰｒｏｃｅｅｄｉｎｇｏｆｔｈｅｓｉｘｔｅｅｎｔｈＨａｗａｉｉＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＳｙｓｔｅｍＳｃｉｅｎｃｅｓ１９８３"，（昭５８−１），Ｐ．２１５−２２４ |
| PROCEEDING OF THE SIXTEENTH HAWAII INTERNATIONAL CONFERENCE ON SYSTEM SCIENCES 1983=S58 * |
Also Published As
| Publication number | Publication date |
|---|---|
| US4698807A (en) | 1987-10-06 |
| NZ207742A (en) | 1988-06-30 |
| EP0142510A1 (en) | 1985-05-29 |
| DE3483455D1 (de) | 1990-11-29 |
| EP0142510A4 (en) | 1987-12-17 |
| JPS60501032A (ja) | 1985-07-04 |
| CA1219965A (en) | 1987-03-31 |
| EP0142510B1 (en) | 1990-10-24 |
| WO1984004225A1 (en) | 1984-10-25 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH0616270B2 (ja) | 自己補修形大規模集積回路 | |
| Negrini et al. | Fault tolerance techniques for array structures used in supercomputing | |
| Jou et al. | Fault-tolerant FFT networks | |
| US5065308A (en) | Processing cell for fault tolerant arrays | |
| Koren et al. | Yield and performance enhancement through redundancy in VLSI and WSI multiprocessor systems | |
| JPH05130101A (ja) | メツシユアーキテクチヤにおける故障許容のための方法と装置 | |
| Wang et al. | Reconfiguration of VLSI/WSI mesh array processors with two-level redundancy | |
| Parhami | Voting networks | |
| Lach et al. | Algorithms for efficient runtime fault recovery on diverse FPGA architectures | |
| AU567251B2 (en) | Self repair large scale integrated circuit | |
| US5261056A (en) | N-port wide bandwidth cross-link register | |
| Majumdar et al. | Fault tolerance in linear systolic arrays using time redundancy | |
| Fukushi et al. | Reconfiguration algorithm for degradable processor arrays based on row and column rerouting | |
| Saucier et al. | Practical experiences in the design of a wafer scale 2-D array | |
| Linderman et al. | A three dimensional systolic array architecture for fast matrix multiplication | |
| Kung et al. | Fabrication-time and run-time fault-tolerant array processors using single-track switches | |
| Noore et al. | Design of reconfigurable fault-tolerant VLSI/WSI processor array structures | |
| LaForge | Feasible regions quantify the configuration power of arrays with multiple fault types | |
| Biswas et al. | Fault tolerance in multiprocessor systems | |
| Lombardi et al. | Reconfiguration of Orthogonal Arrays by Front Deletion | |
| Popli et al. | A Reconfiguration Technique for Reliable VLSI DSP Array Processors | |
| Horiguchi et al. | Self-reconfiguration scheme of 3D-mesh arrays | |
| CHOI | Easily reconfigurable VLSI sorter | |
| Wegner et al. | A distributed 2-fault tolerant control algorithm for reconfiguring fault-tolerant mesh arrays | |
| Hwang | A high reliability two‐level fault tolerant mesh design and applications |