JPH02194457A - コンピユータのためのメモリ装置及びメモリ構成方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 Ａ、産業上の利用分野 この発明は、−船釣には、フェイル・セーフ・コンピュ
ータ・メモリに関する。より詳しくは、この発明は、負
荷平衡されたフェイル・セーフ・メモリを与えるために
、チェックサム・ブロックをメモリ・モジュールに亙っ
てアドレッシング機構が分配し、メモリ・モジュールの
故障の後は、アドレッシング機構が残りのメモリ・ブロ
ックに亙ってチェックサム・ブロックを再分配し、以て
、負荷平衡に近いフェイル・セーフ・メモリを与える、
フェイル・セーフ・モジュラ−・メモリに使用される方
法及び装置を提供するものである。

Ｂ、従来技術 ］ンピュータの能力と可用性に対する必要条件が増大す
るにつれて、計算及び可用性の必要条件をサポートする
ために複数のプロセッサを相互接続することが益々重要
になってきた。典型的には、複数のプロセッサは、相互
接続ネットワークを通じて複数の共用メモリ・モジュー
ルに接続される。

そのようなシステムの可用性条件を満たすためには、あ
るメモリ・モジュールの障害がそのモジュールに含まれ
ているデータの遺失をもたらしたり、システム全体の障
害を引き起こしたりしない、ということが絶対条件であ
る。

モジュラ−・メモリ中のモジュール障害に対する許容性
は、モジュールのうちの１つを、他のモジュールのデー
タのチェックサムを含むチェックサム・モジュールとし
て宣言することによって達成される。すると、モジュー
ル障害の際には、失われたデータが再構成される前に、
２つ以上のメモリ・モジュールが故障していないという
仮定の下で、残りのモジュールとチェックサム・モジュ
ールから失われたデータを再構成することができる。も
し、チェックサム・モジュールが故障したなら、チェッ
クサムは、他のモジュール中のデータから再構成するこ
とができる。そして、メモリの更新の度に、チェックサ
ム・メモリ中のチェックサムは再構成する必要がある。

このことは、単一のｔｌ！１次的メモリ要求ストリーム
しか発生しない単一プロセッサの場合には現実的に利用
できるスキームであるかもしれないが、チェックサムは
、書き込みの度毎に更新されるので、単一チェックサム
・モジュールは、高速で同時的な多重メモリ書き込み要
求ストリームを発生する多重プロセッサ・システムには
ボトルネックであることがわかっている。このため、複
数のプロセッサによって同時にアクセス可能であり、そ
のデータを、あるモジュールの障害の場合に再構成する
ことができるようなフェイル・セーフ・メモリが必要と
される。さらに、システムに対するメモリ・モジュール
の統合または除去が容易でなくてはならない。

次に、上述の問題に対する従来技術の解決策を見てみよ
う。

米国特許第３８７６９７８号においては、１つのディス
ク・メモリが他のディスク・メモリ中にあるデータのチ
ェックサムを記憶する。そして、データが更新される毎
に、チェックサム・モジュール中の対応チェックサムを
更新しなくてはならない。それゆえ、チェックサム・デ
ィスクに対する書き込みトラフィックは、他の全てのデ
ィスクに対する書き込みトラフィックの総和であり、こ
のことは、チェックサム・ディスクにおける（性能）ボ
トルネックにつながる。本発明は、このボトルネックを
正確に解消させるのである。

米国特許第３７４２４５９号には、各メモリ・ワード毎
に固定サイズのコードワードが生成されるようなスキー
ムが記述されている。これにおいては、複数のコードワ
ードがメモリの１つの位置にバックされている。そして
、１つのメモリ位置にバックすることができるコードワ
ードの最大の数が、コードワードを記憶するために必要
な余分のメモリの里を決定する。それとは対照的に、本
発明は、任意の数のワードが、障害許容のための冗長情
報を記憶するための同一の余分のワードを共有すること
を可能ならしめる。米国特許第３７４２４５９号と本願
発明との間の別の根本的な差異は、次のようなものであ
る。すなわち、その米国特許にあっては、データのある
ワードのエラー訂正コードが、過渡的な障害によって引
き起こされたワード中のいくつかのエラーを訂正するこ
とができるようなものである。そして、そのデータ・ワ
ードが位置するメモリ・モジュールが完全に故障してし
まうか、または、ワードのある数取」−のビットが誤っ
ていると、このスキームは最早、データを回復すること
ができない。これとは対照的に、本発明は、モジュール
全体の障害に厳密に対処するように構成されている。

米国特許第４４５９６５８号においては、データベース
回復がシャドー・ベージングによって実現されるような
、データベース中の自由リストを回復するスキームが記
述されている。このスキームは、ＡＣＭ　　Ｔｒａｎｓ
ａｃＬｉｏｎ　ｏｎ　ＤａｔａｂａｓｅＳｙｓｔｅｍｓ
、Ｖｏｌ、２．Ｎｏ、１．Ｍａｒｃｈ　１９７７、ｐｐ
、９１−１０４のＲ，Ａ、　Ｌｏｒｔｅによる、［大規
模セグメント・データベース・システムにおける物理的
完全性（Ｐｈｙｓｉｃａｌ　Ｉｎｔｅｇｒｉｔｙ　ｉｎ
　ａ　Ｌａｒｇｅ　ＳｅｇｍｅｎｔｅｄＤａｔａｂａｓ
ｅ）　Ｊと題する刊行物で概要説明されている。このス
キームにおいては、各データ項目が２つの異なる媒体（
主記憶及びディスク）上の２つの異なるメモリ位置に複
写されており、よってメモリの必要量を２倍にしている
。これとは対照的に、本発明は、冗長情報を記憶するた
めに、もともとのメモリ・サイズの一部しか使用しない
。

米国特許第３７３７８７０号においては、エンコードさ
れたｍＸｎビット・ワードを記憶するために、ｍ＋ｓの
ｎビット・メモリ・モジュールが使用される。モジュー
ルの障害を保護するために、ビット・パリティが使用さ
れる。もしモジュール中の故障が検出されたなら、パリ
ティが破られていることがあるので、パリティ・チエツ
クがターンオフされる。そして、残りの故障していない
モジュールからのビットが読み取られ、スペアのビット
がメモリに統合され、パリティが再計算されてメモリの
内容全体がモジュールの新しい構成（故障していないモ
ジュール及びスペア）に再書込みされる。これにおいて
は、モジュール障害が生じるとメモリの内容を訂正し、
スペア・モジュールのうちの１つを、故障によって失わ
れたばかりのモジュールに置き換えるために自動的にも
ってくるものである。このスキームは、どれかのプロセ
ッサからのメモリ要求毎にすべてのメモリがアクセスさ
れる必要があるので、複数のプロセッサの場合、メモリ
に性能的なボトルネックを呈する。

米国特許第３４３６７３７号においては、ワード毎にｎ
ビットの情報を記憶するために、ｎ個のメモリ・モジュ
ールとともにＳ個のスペア・モジュールを使用すること
が提案されている。これにおいては、ワードの各ビット
が別々のメモリ・モジュールに記憶される。そして、ｓ
＋ｎビットが、エラー訂正または検出のためのＳビット
によってエンコードされたｎビット・ワードをあられす
。

モジュール障害の場合、残りのモジュールから利用可能
なビットが、ワードを再構成するために使用される。こ
れの場合も、メモリ要求毎にｓ　十ｎのずべでのメモリ
・モジュールがアクセスされなくてはならず、以て、本
願発明によって与えられるような、複数のプロセッサか
らの同時的な要求にサービスすることが阻止されてしま
う。

本出願人に係る、１９８７年７月２日出願の米国特許出
願第０６８８６２号においては、チェックサム・スキー
ムをもつメモリのモジュラ−構成が記述されている。こ
れにおいては、どれかのメモリ位置が更新される毎に、
この位置に対応するチェックサムもチェックサム中で更
新されなくてはならない、チェックサムに対する書き込
みトラフィックは、すべてのデータ・モジュールに対す
る書き込みトラフィックの総和である。それゆえ、すべ
てのモジュールを設計するのに同一の技術が使用されて
いるなら、チェックサム・モジュールは、ある相当な利
用レベルでボトルネックである。

それの代替案は、より高位グレードの技術のチェックサ
ム・モジュールを形成し、それに追加的な帯域を与える
ことである。しかし、それはメモリのコストを増大させ
てしまう。

米国特許第４０９２１３２号においては、アクセスの単
位がルコードであるゆそして、１°つのレコードが複数
のセグメントに分割され、チェックサム・セグメントが
付与される。このレコード・セグメントとチェックサム
は、異なるディスク・ドライブ上にある１、このとき、
任意の読み取りまたは書き込みアクセス毎に、全てのセ
グメン１が読み書きされる。このことは、１゛つのアク
セスが、レコード・セグメント・ドライブとチェックサ
ム・ドライブのめいめいで、シーク＋潜在→−転送時間
をもたらすことを意味する。このことは、ディスク」こ
の大きい負荷とスルーブッ［の低ドにつながる。これに
対して、本発明のアクセスの単位は、単一のメモリ・モ
ジュールに配、置されているデータのブロックである。

そのブロックの絹は、いくつかの異なるメモリ・モジュ
ールＦに配置ηされた共通のチェックサムをもつ、この
とき、各アクセスは、アクセスされているメモリ・モジ
ュールとチェックサム・モジュールにのみ関与する。

このスキームの相違は、著しい性能上の差異につながる
。

Ｃ８発明が解決しようとする問題点 この発明の目的は、完全に単一の技術から実現されたと
きにさえも良好な性能をもつメモリ・ユニットの全体的
な障害の場合にデータの再構成を可能ならしめるフェイ
ル・セーフ・メモリ・システムを提供することにある。

この発明の他の目的は、多重プロセッサ・システムにお
ける使用に適したフェイル・セーフ・メモリ・システム
を提供することにある。

この発明のさらに他の目的は、チェックサムを書くこと
によって引き起こされるボトルネックを低減するチェッ
クサム方法を使用したフェイル・セーフ・メモリ・ユニ
ットを提供することにある。

この発明のさらに他の目的は、単一のメモリ・モジュー
ルの故障の際にデータを回復するためのチェックサム方
法を使用したフェイル・セーフ・メモリ・ユニットのた
めの方法を提供することにある。

この発明のさらに他の目的は、データを再分配しメモリ
・モジュールの障害時にチェックサムを再分配するため
にチェックサム方法を使用したフェイル・セーフ・メモ
リ・ユニットのための方法を提供することにある。

Ｄ１問題点を解決するための手段 本発明に従えば、チェックサムが、単一のモジュールに
記憶されるのではなくて、複数のモジュールに亙って分
配されるような、物理的メモリのための新規なアドレッ
シング・スキームが提供される。このようにして、メモ
リ・モジュールに対する書きこみアクセスは乱数化され
、単一チェックサム・モジュールの性能上のボトルネッ
クが除去される。

メモリの更新毎に、更新された位置に対応するチェック
サムは変更しなくてはならない。このとき、チェックサ
ムは複数のメモリ・モジュールに亙って分配されている
ので、本来的にボトルネックとなる単一のメモリ・モジ
ュールは存在しない。

Ｅ、実施例 第１図は、プロセッサ３０ａないし３０ｐ、！：、相互
接続構造２０と、本発明を具体化するメモリ・モジュー
ル１０ａないし１０ｍのブロック図である。これにおい
て、複数のプロセッサ３０ａないし３０ｐ（ｐは任意の
正の整数である）が、相互接続構造２０を介して複数の
メモリ・モジュール１０ａないし１．Ｏｒｎ（ｍは任意
の正の整数である）に接続されている。このとき、プロ
セッサの数とメモリ・モジュールの数は、異なっていて
もよいことに留意されたい。各プロセッサ３０ａないし
３０ｐは、プロセッサ・アダプタ１０ａないしｌＯｍを
介して相互接続構造に接続され、同様に、各メモリ・モ
ジュール１０ａないし１０＋ｎは、メモリ・アダプタ１
５０ａないし１５０ｍを介して相互接続構造に接続され
でいる。

第１図では、Ｍ、ないしＭ　＠　＋　１　と指定され、
１０ａないし１００ｍとラベルされた、ｍ個のメモリ・
モジュールの場合が示されている。各メモリ・モジュー
ル、例えば１０ａは、ＳｏないしＳ、−１と指定され、
１００−１ａないし１０−ｍａとラヘルされたｍ個の区
画に分けられている。各、メモリ・モジュールにおいて
、１つの区画Ｓｋは、データを含む他の全てのメモリ・
モジュールと同一の数の区画のチェックサムを含む。例
えば、ｌＯａとラベルされたメモリ・モジュールＭ、に
おいて、１００−１ａとラベルされた区画Ｓ０が、それ
ぞれ１０ａないし１０ｍとラベルされた他の全てのメモ
リ・モジュールＭｌ・・・・・・Ｍａ−１の、１００−
１ｂ、・・・・・・１００−１ｒｎとラベルされた区画
Ｓ０に含まれるデータのチェックサムを含む。

こうして、−船釣に、メモリ・モジュール間イ。

において、区画Ｓｉは、データを含む他の全てのモジュ
ールの区画Ｓ、をバックアップするチェックサム区画で
ある。このスキームは、メモリ・モジュール毎の任意の
数の区画を含むように以下で一般化される。

この説明では、メモリ・アクセスがサイズＢのデータの
ブロックの単位で行なわれる、と仮定している。Ｂの典
型的な値は、４Ｋ（すなわち、４０９６）バイトのデー
タである。より詳しく述べると、メモリ・モジュール（
上記を参照）の各区画は、データの整数個のブロックに
分割される。

この分野の当業者は、本発明が、データのブロックの任
意のサイズに容易に適合できることを理解するであろう
。この説明は、任意の個数Ｎのプロセッサについてなさ
れている。また、この分野の当業者は、本発明が、プロ
セッサがメモリに対して複数の目立った要求を行なうこ
とができるような、単一のプロセッサ（すなわち、Ｎ−
１）の場合にも容易に適用できることを理解するであろ
う。

第２図は、メモリ・モジュールに含まれているデータ・
ブロックのアドレス２００の解釈を示す図である。より
詳しく述べると、（すべてのメモリ・モジュールの）全
体のアドレス空間は２にブロックのデータであると仮定
されており、これがＭ＝２”のメモリ・モジュール間で
等しく分配されている。ここで、ｋ及びｎは正の整数で
あり、ｋは２ｎ以上であることが必要である。こうして
、各メモリ・モジュールは２に−７のデータ・ブロック
を含む、どれかのブロックをアドレスするためには、メ
モリ・モジュールと、そのメモリ・モジュール内に含ま
れている区画と、その区画内に含まれているデータ・ブ
ロックを選択するアドレスが決定される。そのようなア
ドレスの構造が第２図に示されている。

第２図に示されているように、任意のブロックのにビッ
ト・アドレスは、ａｌとして示された２１０と、ａ２と
して示された２２０と、ａ３として示された２３０に分
割される。フィールド２１０（ａｌ）は、ｎビットであ
り、フィールド２２０（ａ２）もｎビットであり、フィ
ールド２３０（ａ３）は、ｋ−２ｎビツトである。より
詳しく述べると、アドレスの上位ｎビットがフィールド
２１０（ａｌ）を構成し、次のｎビットがフィールド２
２０　（ａ２）を構成し、下位に一２ｎビットがフィー
ルド２３０　（ａ３）を構成する。フィールド２２０（
ａ２）は、メモリ・モジュール・アドレスをあられす。

すなわち、もし７フイールド２２０　（ａ２）の２値表
現の値がｉであるなら、アドレスされたブロックは、メ
モリ・モジュールＭ、中にある。また、フィールド２１
０とフイール（２３υの連結は、メｉ靭トモジュールＭ
　、　ｚ　内のアドレスされるブロックの２値アドレス
を表す、このように、フィールド２１０はフィールドａ
２によって決定されたメモリ・Ｌ−ジュール内の区画の
アドレスをあられし、フィールド２３０ば、フィールド
２１０によって決定される区画内のブロク、りのアドレ
スをあ・）わず。ずなわち、もしａｌの２値表現がｊで
あるなら、アドレスされるブロックは区Ａ　Ｓ　Ｊにあ
り、もしフィールド２３０の２値表現、がｑであるなら
、区画Ｓ４内のｑ番目のブロックがアドレスされる。

フィールドａ】、ａ２及びａ３内の７ドＬ／スからチエ
ツクＪＪ−１，・アドレスが生成される様子は、次のと
おりである。ずなわぢ、モジュールＭ０の区画Ｓ□の変
位ａ３に対応するチェックザＪ、・フロックが見出され
る。このように、アドレスａ１＝ａ２をもつブ１１ツク
がチェノ・クサム・フロックである。これらのチェック
サム・ブロックは、データには使用されない。この分野
の当業者は、システムが初期化される時に、これらのブ
ロックを利用可能なブロックのプールから除外すること
によって、このことが容易（こ達成されることを理解す
るであろう。これにより、これらのブロックは、仮想ペ
ージをメモリの物理的ブロックに割当”ζる時にオペレ
ーティング・システムによって使用されることがなくな
る。ａｉ　　ａｘ　ａ、によ・つ７ア（′１ノスされる
チェックサム、８すなわちメモリ・工ジュールＭ　＋１
１　％区画Ｓ１及びｐこ（◇、ｊ３にあるチェックサム
’Ｅ　Ｃ１１１７１３とあられすことにする。−・船釣
に、チェックサム・グロックは、ａｌ＝ｉ、ａ３＝ｊと
して、Ｃ４，、と示される。同様に、データブロックは
、ａｌ−１、ａ２＝ｊ、ａ３＝にというフィールドによ
り、、Ｄｉｊｋ　と示される。フロラ・７（’、、、で
のチェックサムは次のように示される。

Ｃｉｉｊ　＝　Ｄ　ｉｏｊ　（Ｄ　Ｄ　ｉｌｊ　ｃｆｌ
”’　Ｄ　ｉ　ｔｉ−１＋　ｊ■Ｄｉ＋・・ｌｌｊ”’
■Ｄ　（ａ−１＋・すなわち、チェックサム（二、は、
モジュールＩＪＯ１ｔ’Ｊ＋　”’Ｍ　＋ｉ−＋＋　、
Ｍ　ｔｉ−ｔｉ　”’Ｍ　＋ｑ−１１のアトし・スｉｊ
で１べてのブロックのビット的なモジュロ２加算を行う
ことによってｊｉＩられる。

モジュールにのグロックＤ　ｉ　ｊ　ｋが新しい値り４
４、に更新されたとき必要なチェックサムＣ１４，は、
次のようＬこして効率的に得られる。

すなわち、 Ｃｉ　ｉ　ｊ　＝　Ｄ　ｉ　ｏ　ｊ　ｌ→Ｄ　ｉ　Ｉ　
ｊ・・・■Ｄ、□・・・■Ｄｉｆｉ−１１ｊ■Ｄ、（、
・ｌｌｊ”’■Ｄ直ｎ−１！、・・・（℃Ｄ　ｉ　ｌｓ
−１１ｊ　　）このように、この方法は、データ及びそ
のチェックサムを記憶するために相互接続構造２０に亘
って２回の転送しか必要としない。すなわち、その第１
の転送はメモリ・モジュールに対する新しいデータＤ　
ｉ　ｊ　ｋの転送であり（そこで、新しいデ２加算）を
行なわれる）第２の転送は、ｒｉＨ分的チックサムＣ３
４，を得るために占いチェックサム第１図の場合におい
ζ、ブ１−！セッサ３０によるグロックの読み取りアク
セスの場合、グａセウサ３０は、ブロック・アドレス（
すなわち、フィールドａｌ　、ａｍ及びａ、）と、読取
り要求を示すコマンド・コードをプロセッサ・アダプタ
３３０に与える。プロセッサ・アダプタ３３０は、この
アドレスとコマンド・コードを相互接続ネットワーク２
０に提供し、ネットワーク２０はプロセッサ・アダプタ
３３０を選択されたメモリ・千ジ１−ル（Ｍ　−ｔ　）
のメモリ・アダプタ１．５０に接続するためにフィール
ドａｍ　２２０　（第２図）を使用する。この接続が成
功裡に確立されたと仮定すると、メモリ・アダプタ１５
０が次に、メモリ・モジュール（Ｍ＠ｚ）１０からのフ
ィールドａ、（２１０）及びａｍ　　（２３０）によっ
てアドレスされるブｌ】ツクを検索し、ぞのブしノック
を、同一゛の接続を介してブロセ゛ソザ・アダプタ３３
０に転送する。

プロセパｌ廿・アダプタ３３０は次に、ブ１１ｆ！ツー
町、）３２０によって示された位置で、フ“ｉ’、Ｊ　
（！ツザの局ｎｊ　、、、Ａモリ３１０中にブ１コック
を格納４″る２デ〜タ転送の結電１、相互接続構造は、
ブロセツ村　アダプタ３３０とメモリ・アダツー□゛・
°１５０の間の接続を解除する３ｔうごこ通知される３
尚、メモリＩＯに対”・する読取りアクセスの場合５、
チェックサム・ブロックは関辱しないことに留意された
い。

もし相互接続構造２（）が選ｆＲされたメモリ・アダプ
タ１５０に対する接続を確立することができない場合は
、そのことが要求元プロセッサ・アダプタ３３０に表示
される。プロセッサ°・アダプタ３３０は次に、適当な
待Ｎ　（ｂａｃｋ−ｏｆｆ）期間の後接続要求を再試行
する。

プロセッサ３２０によるＩモリ１０への書込みアクセス
の場合、ブｌＪセッサ３２０が書込みブロック２００の
アドレス（すなわち、フィールｌ”　ａ　＋　、ａ２及
びａ、）と、書込み要求を示すコマンド・コードとをプ
ロセッサ・アダプタ３３０に配置するａ書込みアクセス
の場合１．ブ１コセツサ・アダプタ。１３０がこのアト
Ｉノス２００とコマニ／ド・コードとを相互接続ネット
ワーク２０に送り、相互接続ネットワーク：２（）は、
グ【」セ・：ノサ・アダツ°り；３３０を５２選択され
たメモリ・モジュール（Ｍ、２）のメモリ・アダプタに
接続するためにフィール）ａ、　　（２２０）を使用す
る。接続が成功裡に確立されたと仮定づると、メモリ・
アダ７゛夕］、　５０は、このブロックのチェックサム
を含むメモリ・モジュール（Ｍ□）１０を決定するため
にフィールド（ａｌ）２１０を使用する。次に、メモリ
・モジュール（Ｍ、、）１０は、必要なチェックサム区
画を含むメモリ・モジュール（Ｍ、、）１０に対し７て
接続を確立することを試みる。もしこの接続を確立する
ことができなかったならば（すなわち、チェックサム区
画を含乙メ七り・モ・：５フユール１．　Ｏがこの時点
でビジーである）、メモリ・アダプタ１５０はブロモ・
ン号・アダプタ３３０に１じ・ジー」であることを通知
し、ブロモ・ンサ・アダプタ３３０との接続が相互接続
ネットワーク２０によって解除される。ぞして、この書
込動作の全体が、待機（ｂａｃｋ−ｏｆｆ）期間と呼ば
れる期間を待った後、再試行される。もしチェックサム
区画を含むメモリ・モジュール１０に対する接続が確立
されたなら、メモリ・アダプタ１５０はプロセッサ・ア
ダプタ３３０に、「処理継続」を通知する。プロセッサ
・アダプタ３３０は次にプロセッサ３０の局所メモリ３
１０からデータ・プロ゛ンクを検索し、ごのブロックを
メモリ・アダプタ１５０に転送する。メモリ・アダプタ
１５０は、メモリ区画とその区画内のデータ・ブロック
を選択するために、フィールド（ａｔ）２１０及びフィ
ールド（ａ３）２３０を使用する。パイプライン技術を
用いると、メモリ・アダプタ１５０は、チェックサム・
メモリ・モジュール（Ｍ、、）１０に転送される部分的
チェックサム（Ｄ；ｂｉ■Ｄｉｂｊ　）の発生と、メモ
リ・モジュール（Ｍ、り１０への新し７いデータＤ；：
τの格納を同時に行う。チェックサムを含むメモリ・モ
ジュール（Ｍ、ｌ）　１０において、メを検索して、そ
れを受領した部分的チェックサム（Ｄ　ｉｋＪ■Ｄ、。

）と排他的論理和し、チェックサムＣｒ　ｉ　ｊのかわ
りに格納される新しいチェックサムを発生する。

第３図を参照すると、ある１つのメモリ・モジュー・ル
またはどれかのサブユニットにおける部分チェックサム
発生のための実施構成が示されている。このような構成
は、適当な制御システムをもつメモリ・チップ中に集積
することができる。面、この構成は、データを含むメモ
リ・モジュールと、チェックサムを含むメモリ・モジュ
ールの両方に通用することができる。プロセッサのため
にフェッチすべきデータはメモリ５５０からフェッチさ
れ、レジスタ５６０からのＯと排他的ＯＲされ、このこ
とはデータかもとの値を保持することを可能ならしめる
。このデータはレジスタ５８０にセーブされ、そこから
、データはボート５３０を介してプロセッサ・アダプタ
３３０に転送される。

書込むべきデータは、ボート５３０上で相互接続構造２
０から受信され、レジスタ５４Ｏにセーブされる。結果
はレジスタ５８０にセーブされ、そこから、データは、
ポート５３０を介してそのチェックサム・データを含む
メモリ・モジュールに転送される。それと同時に、新し
いデータがレジスタ５４０からメモリ５５０へ格納され
る。そのチェックサムを含むメモリ・モジュールでは、
対応する（排他的論理和された）データが゛関−ト５３
０で受信され、レジスタ５４０にセーブされる。

古いチェックサム・データがメモリ５５０からフェッチ
され、ゲート５７０でレジスタ５４０．のデータと排他
的ＯＲされる。その結果はレジスタ５８０にセーブされ
る。レジスタ５８０中のデータは、レジスタ５４０に転
送され、新しいチェックサムとしてメモリ５５０中に格
納される。この分野の当業者なら、レジスタ５８０中の
データを直接メモリ５５０中に格納できることを理解す
るであろう。この様にして、新しいブロックとチェック
サム・ブロックの全体が対応するデータとチェックサム
・メモリに書込まれる。こうして、データ・メモリに対
する更新と、チェックサム・メモリに対する更新が同時
に、バイブライン的に生じる。最後に、データ及びチェ
ックサム・ブロックの書込みが完了したとき、メモリ・
アダプタ１５０とプロセッサ・アダプタ３３０の間の接
続が解除される。

この分野の当業者なら、メモリ・モジュールへの検索及
び格納の単位が任意のバイト数でよいことを認識するで
あろう。上述の動作は、説明上の例示にすぎない。

次に、メモリ・モジュールの故障後の動作について説明
する。ここで、メモリ・モジュールＭｉが故障し、シス
テム構成から除外されたと仮定する。故障を検出すると
、故障のメモリ・モジュール中の各ブロックの内容が、
他のメモリ・モジュール中の対応ブロックの内容と排他
的ＯＲを実行することにより再生される。この分野の当
業者なら、これらの再生されたブロックをブロックの仮
想アドレスによって決定されるディスク記憶上の対応ブ
ロックに書き出すことができる（ただし、そのブロック
のコピーが既にディスク上に存在している場合は別であ
る）ことを理解するであろう。

このようにして、故障メモリのすべてのブロックがディ
スクに書かれる。失なわれたモジュールの各ブロックが
再構成されたとき、それは、現存メモリ・モジュールの
チェックサムに対応する新しいチェックサムを生成する
ために、チェックサムの現在の値と排他的ＯＲされる（
もしブロックの転送の間にメモリ・モジュールの故障が
生じたなら、そのブロックは古いチェックサムからは再
構成することができないけれども、従来技術で知られて
いるように、それは、適切な通知を使用して、送信側プ
ロセッサから検索することができる）。

ここでメモリは、故障メモリ・モジュール中、中にあっ
た区画Ｓ、を除く各区画に対応するチェックサムをもつ
。このメモリは今や、チェックサム・ブロックが故障メ
モリ・モジュールにあるようなブロック書込みが生じた
場合に、新しいデータ・ブロックがチェックサム生成を
伴うことなく単に書込まれることを除いては、前述と同
様に動作することができる。故障メモリ・モジュールＭ
！が修理されシステムに戻されるべきときには、そのす
べてのブロックが最初にすべてゼロに初期化される。次
に、他のメモリ・モジュールの区画Ｓ」の対応データの
排他的論理和を実行することによって区画Ｓ、のチェッ
クサムが再生される。次にシステムは、すべての区画を
バックアップされた、前述の正常動作に戻る。

上述の段階で説明した障害再構成では、メモリ・モジュ
ールＭ１が故障した後は、区画Ｓ、はチェックサムをも
たない。それゆえ、そこで故障メモリ・モジュールがシ
ステムに再構成される前に別のメモリ・モジュールの故
障が生じると、故障メモリ・モジュールの区画Ｓ、のデ
ータは失われてしまう。次に示す再構成スキームは、チ
ェックサムのアドレスと位置を変更し、以て、メモリ・
モジュールとメモリ再構成の故障の後、すべての区画が
バックアップ・チェックサムをもつようにし、以て、再
構成の後、別のメモリ・モジュールが故障しでもデータ
が失われないようにするものである。すなわち、メモリ
・モジュールＭ、の故障の後、その故障モジュールに以
前に割当てられていた区画Ｓ、のチェックサムは、非障
害モジを一ルに割当て゛られなくてはならない。このこ
とは６、区画Ｓ、のチェックサムを見出すためζ、こ１
、千ジュールＭ　；　＋　）　ｎｏｄ　ｍを選択するこ
とによって実行される。もしＭ　ｉｌｌ　１ｌｉｏｄ　
ｌ１１がやはり故障上ジュールであ・つたなら、モジュ
ー・ルＭ１４．　ｆｆ１ｏｄ　ｌｌｌが選択される、等
である。より詳しく述べると、ｃｙｃ（ａｌ）と呼ばれ
る簡単な関数が定義され、これは、モジュール・アドレ
スが、現存メモリ・モジュールのａｌと等しいかそれよ
りも大きい（巡回的に）最小のアドレスであるようなモ
ジュールである。すなわら、もしメモリ・モジュールＭ
□が活動的ならｃｙｃ（ａｌ）がａｌに等しく、そうで
な（、もし、モジュールＭ　ｔａｉ＋ｎｌｌ！Ｏｄ　ｍ
が活動的なら、ｃｙｃ（ａｔ）がａｌに等しくなる、等
である。ブロック（ａｌ、ａ２、ａ３）は、モジュール
Ｍ１が非故障ブロックである場さにのみ存在する。その
チェックサムは、位置（ａＬｅｙｃ　　（ａｌ）、ａ３
）に見出される。（ａｉ、ｃｙｅ　　（ａｌ）、、ａ３
）のすべての位置はチェックサムを含み、システムのＩ
ＰＬの間に見逃されるメモリ・モジュールＯご亘る物理
メモリ・アドレスおともに利用不可能とし、でマークさ
れる。それゆえ、もしメモリ・モジュールＭｌが見）ル
されるなら、（ａｌ、ａ２、ａ３）という形式のすべて
のアドレスは、アドレス空間から見逃されるものとして
マークされることになる。第４図には、メモリ・モジュ
ールＭ、の障害の前後のメモリ・アドレシング・スキー
ムが与えられている。障害の前には、第４ａ図に示すよ
うに、４つのメモリ・モジュール（１０ａＳ　１０ｂ、
ｔ。

Ｃ及び１０ｄ）からなるメモリ・システムが存在してい
る。３つの区画モジュール１０ｂ、１０ｃ及びＮｏｄ中
の１００−１ｂ、１００−１ｅ、１００−１ｄのチェッ
クサムはそれぞれ、モジュールｔＯａの区画１００−１
ａ中に含まれている。

同様に、区画１００−２ａ、１００−２ｃ及び１００−
２ｄのチェックサムは区画１００−２ｂ中に格納されて
いる。区画１００−３ａ、１００３ｂ及び１００−３ｄ
のチェックサムは、区画１００　２　ｂに格納されてい
る。最後に、区画１００−４ａ、１００−４　ｂ及び１
００−４　ｃのチェックサムが区画１００−４ｄに格納
されている。

各モジュールは、等しい数のチェックサム区画をもつ。

さて、メモリ・モジュール故障後の動作は次のとおりで
ある。すなわち、初期動作は、前述の故障の場合と全く
同じである。ここで再び、メモリ・モジュールＭ８が故
障し、システム構成から外されたと仮定しよう。その故
障を検出すると、他のメモリ・モジュール中の対応する
区画の内容を排他的ＯＲすることにより、障害メモリ・
モジュール中の各区画の内容が再生される。以前と同様
に、これらの再生された区画はページの仮想アドレスに
よって決定されたディスク記憶上の対応空間に書き出す
ことができる（ただし、その区画が既にディスク上に存
在している場合を除く）。このようにして、故障メモリ
のすべての区画がディスクに書かれる。特に、第４図の
モジュール１０ｂの故障について考慮してみよう。失な
われたデータは次のようにして再生される。すなわち、
区画１００−１ｂのデータは、区画１００−１ｃと、区
画１００−１ｄと、チェックサム１００−１ａのデータ
の内容を排他的論理和することによって再生される０区
画１００−３　ｂのデータは、区画１００−３ａ、１０
０−３ｄ中のデータ及びチェックサム１００−３ｃを排
他的論理和することにより再生される。区画１０（１−
４ｂのデータは、区画１００−４ａ、１００−４ｃのデ
ータ及びチェックサム１００−４ｄを排他的論理和する
ことにより再生される。失なわれたモジュールの各デー
タ区画が再構生されたとき、それは、非障害メモリ・モ
ジュール中のデータ・セグメントのチェックサムに対応
する新しいチェックサムを作成するために、そのチェッ
クサム・セグメントの現在の値と排他的論理和される。

第４図の例では、区画１ｏｏ−ｉｂに対応して再生され
たデータが、区画１００−１ｃ及び１００−１ｄの新し
いチェツクサムを形成するために区画１００〜１ａと排
他的論理和されて、区画１００−１ａに格納される。区
画１００−３　ｂとして再生されたデータは区画１００
−３ｃと排他的論理和され、そこに格納される。区画１
００−４　ｂとして再生されたデータは、区画１００−
４　ｄと排他的論理和されてそこに格納される（ｆｖ１
述と同様に、もしブロックの転送の間にメモリ・モジュ
ールの障害が発生したなら、そのブロックは、チェック
サムから再構成できないけれども、適当な通知を用いて
、送信側プロセッサから検索することができる）。

データが再生されチェックサムが再計算された後は、そ
のメモリは、障害メモリ・モジュールＭ、中で見出され
た区画Ｓ、を除いて各区画に対応するチェックサムをも
つ。区画Ｓ１のチェックサムは、モジュールＭｃｙｃ（
ｉ）中に配置されることになる。モジュールＭｅｙｃ（
ｔ）の区画Ｓ、は、ディスクに書き出される。第４図の
例では、区画１００３Ｃはチェックサム区画に変換され
る。そして、区画１００−１ｂ、１００−２ｂ、、１０
０−３ｂ及び１００〜４ｂと１００−３ｃはコンピュー
タ・メモリの物理的アドレス空間から除去され、区画１
００−３ｅのデータがディスクに書かれる。

新しいチェックサム区画位置が第４ｂ図に示されている
。区画Ｓ、のチェックサムは、モジュールＭｃｙｃ（ｉ
）を除く現存するすべてのモジュール中の区画Ｓ、中の
データを排他的ＯＲすることによって作成される。１つ
の例では、区画１００−３ａ及び１００−３ｄのチェッ
クサムが計算されて区画１００−３Ｃに格納される。す
ると、今やすべてのチエツク４ｊムは可用であって再構
成は完了している。尚、この分野の当業者なら、上記の
例を、任意の数のメモリ・モジュール及び区画に一般化
することができよう。

再構成後の読み書き動作は、もしチェックサムが故障モ
ジュールＭ、にあると計算されたなら、それがモジュー
ルＭｃｙｃ（ｉ）に配置されることを除いては、すべて
のメモリ・モジュールが活動性である場合と同一である
。いくつかのメモリ・モジュールが活動的でないときは
、わずかな量の負荷非平衡が存在する。というのは、す
べてのメモリ・モジュールがチェックサムを含むけれど
も、チェックサムは均等に分割されないからである。そ
のような偏りがあまり大きくなく、また病的な例外を除
いて、このスキームは、すべてのチェックサムが単一の
メモリ・モジュールに格納された場合のスキームよりも
相当に優れた性能を示した。

−ト記の説明では、モジュール及びチェックサムの位置
決めピッ）　（ａ　１．ａ２）がブロック・アドレスの
最上位ビットであったが、そのアドレッシングは、これ
らのビットがブロック・アドレスの「中位」ビットであ
るように容易に一般化することができる。すると、アド
レスは、（ａＯ，ａｌ、ａ２、ａ４）のように表現する
ことができ、ここで、モジュール番号はａ２によって決
定され、モジュール内のアドレスは（ａＯＳａｔ、ａ３
）によって決定され、ブロック（ａｏ、ａｌ、ａ２、ａ
３）のチェックサムはブロック（ａ　Ｏ−、ａ　１、ａ
ｌ、ａ３）に存在する。例えば、ａ３が１２ビツトなら
、モジュールに亘って４に個のブロックが介在配置され
ることになり、チェックサムはモジュールに亘って均等
に分布されることになる。

異なるプロセッサは比較的ランダムに複数のモジュール
に亘って異なる区画にアクセスする傾向にあるので、こ
のことは、モジュールに亘る負荷平衡を改善させる傾向
をもたらす。

Ｆ１発明の詳細 な説明したように、この発明によれば、チェックサムを
複数のモジュールに亘って均等に分散させたので、プロ
セッサのアクセスの集中によるボトルネックの解消され
たメモリ・システムが提供される。

【図面の簡単な説明】

第１図は、本発明を実現する装置の全体の概要を示すブ
ロック図、 第２図は、データ・アドレスを生成するだめの各フィー
ルドを示す図、 第３図は、古いデータと、古いチェックサムと、新しい
データ・ブロックから新しいチェックサムを生成するた
めの回路構成のブロック図、第４ａ及び第４ｂ図は、メ
モリ・モジュールのうちの１つの障害の後、チェックサ
ム・アドレスが発生される様子を示す図である。

Claims (2)

【特許請求の範囲】
1. （１） （ａ）各々が複数のデータ・ブロックからなり、該メモ
   リ・ブロックがアクセスの単位である複数のメモリ・モ
   ジュールと、 （ｂ）等しいサイズの複数の上記データ・ブロックから
   なる複数のグループを識別し、該複数のデータ・ブロッ
   クを上記メモリ・モジュールに割当てるための手段と、 （ｃ）上記識別された等しいサイズのデータ・ブロック
   の少なくとも１つをバックアップ・ブロックとし、以て
   、それを、該バックアップ・ブロック以外の上記等しい
   サイズの複数のデータ・ブロックからなる上記グループ
   の上記データ・グループのためのバックアップ・ブロッ
   クとして認識するための手段と、 （ｄ）上記異なるグループの上記バックアップ・ブロッ
   クを、上記複数のメモリ・モジュールに亙つて分配する
   ための手段と、 （ｅ）上記１つのデータ・ブロックのグループ内の全て
   のデータ・ブロックの内容のチェックサムとして、１つ
   のグループの上記バックアップ・ブロックの内容を計算
   するための手段と、 （ｆ）上記チェックサムを、上記グループの上記識別さ
   れたバックアップ・ブロック中に格納するための手段と
   、 （ｇ）上記１つのメモリ・モジュールの故障が生じた場
   合に、上記バックアップ・ブロックにおけるチェックサ
   ムと、他の故障が生じていないメモリ・モジュールの識
   別されたデータ・ブロックからのデータから、該故障が
   生じたメモリ・モジュールに記憶されていたデータを計
   算するための手段とを具備する、 コンピュータ・システムのためのメモリ装置。
2. （２）複数のブロックからなるグループをもち、該ブロ
   ックのグループが少なくとも１つのバックアップ・ブロ
   ックとデータ・ブロックからなり、上記各メモリ・モジ
   ュール中の上記ブロックが様々なアドレス・ラベルをも
   ち、アクセスの単位がブロックである、コンピュータ・
   システムのためのメモリに障害耐性を与えるための方法
   において、（ａ）異なるブロックのための上記バックア
   ップ・ブロックを上記メモリ・モジュールに亙つて分配
   する段階と、 （ｂ）ブロック中のデータのアドレス・ラベルと、上記
   データ・ブロックのバックアップ・ブロックのアドレス
   ・ラベルを識別するためにアドレス発生手段を与える段
   階と、 （ｃ）ブロックの１つのグループの全てのデータ・ブロ
   ックの内容に従つて各メモリ・ブロックの内容のチェッ
   クサムを計算する段階と、 （ｄ）識別されたアドレス・ラベルをもつ識別されたバ
   ックアップ・メモリ・ブロックに上記チェックサムを格
   納する段階と、 （ｅ）あるメモリ・モジュールが故障した場合に、非故
   障メモリ・モジュール中の識別されたブロックから、該
   故障メモリ・モジュールのブロックのデータを計算する
   段階を有する、 コンピュータ・システムのためのメモリ構成方法。