リダンダンシ演算装置及びリダンダンシ演算方法並びにメモリ試験装置
【課題】メモリデバイスの構造に依存しない汎用性を備えると共にリダンダンシ演算の高速化を図り、メモリデバイスの救済率の向上を図る。
【解決手段】全てのフェイルが救済されるための条件を第１の制約条件とし、同一の救済能力を有するスペアラインの集合であるスペアライングループ毎に使用されるスペアラインの本数を制限するための条件を第２の制約条件とし、フェイルの救済に使用されるスペアラインの総数、またはスペアラインをフェイルの救済に使用した場合に発生する総コストを目的関数とし、前記第１及び第２の制約条件の下、前記目的関数を最小化するという最適化問題を０−１整数計画法を適用して解くことにより、前記メモリセル領域におけるフェイル分布に対する前記スペアラインの割当パターンを求める。
【解決手段】全てのフェイルが救済されるための条件を第１の制約条件とし、同一の救済能力を有するスペアラインの集合であるスペアライングループ毎に使用されるスペアラインの本数を制限するための条件を第２の制約条件とし、フェイルの救済に使用されるスペアラインの総数、またはスペアラインをフェイルの救済に使用した場合に発生する総コストを目的関数とし、前記第１及び第２の制約条件の下、前記目的関数を最小化するという最適化問題を０−１整数計画法を適用して解くことにより、前記メモリセル領域におけるフェイル分布に対する前記スペアラインの割当パターンを求める。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、メモリデバイスにおける不良セルを予備セルで置換するリダンダンシ処理を行う上で、不良セルに対する予備セルの最適な割当パターンを演算によって求めるリダンダンシ演算装置及びリダンダンシ演算方法並びに当該装置を備えるメモリ試験装置に関する。
【背景技術】
【０００２】
ＲＡＭ（Random Access Memory）等のメモリデバイスは、製造時においてメモリセルに１つでも欠陥があると不良になる。このため、通常は、本来メモリセルとして用いられるセル領域の周囲に予備セルを形成しておき、メモリ試験装置の試験によってメモリデバイスに欠陥が生じた（フェイルと判定された）不良セルが検出された場合、レーザトリマ等によってメモリデバイス内の所定のパターンを切断して、不良セルを予備セルで置換して不良デバイスを救済することにより、製造歩留まりの低下を防止している。このように、メモリデバイスにおいて不良セルを予備セルで置換する処理をリダンダンシ処理という。
【０００３】
このような予備セルによる置換は、図９に示すように、ライン単位で行われることが一般的である。図９は、メモリデバイスに形成されるメモリセル及びその周囲に形成された予備セルを概念的に示す図である。図９において、符号１００を付した矩形領域は複数のメモリセルが２次元配列されたメモリセル領域を表しており、このメモリセル領域１００内の個々のメモリセルは列アドレス（Ｘアドレス）と行アドレス（Ｙアドレス）とによって特定される。メモリセル領域１００の内部に示した記号「×」は、メモリ試験装置の試験によってフェイルと判定された不良セルを表している。
【０００４】
図９に示す例では、メモリセル領域１００の図中右側に、Ｙアドレス方向に延在するスペアライン（ライン状にＹアドレスの数だけ形成された予備セルの集合体）が複数本用意されており、メモリセル領域１００の図中下側に、Ｘアドレス方向に延在するスペアライン（ライン状にＸアドレスの数だけ形成された予備セルの集合体）が複数本用意されている。ここで、同一の救済能力を有するスペアラインの集合をスペアライングループという。
【０００５】
例えば、図９において、Ｙアドレス方向に延在する複数のスペアラインの各々は、Ｘアドレス方向に移動し、メモリセル領域１００においてＹアドレス方向に存在する不良セル（例えば符号Ｃ１１のライン上の不良セル）を同時救済する能力がある。なお、スペアラインの移動とは、実際に物理的に移動するという意味ではなく、置換によって擬似的に移動しているように見えることを指す。このように、Ｘアドレス方向を移動範囲とし、Ｙアドレス方向に存在する不良セルの同時救済能力を有するスペアラインの集合を、スペアライングループＸＳＬＧと呼ぶ。また、図９において、Ｘアドレス方向に延在する複数のスペアラインの各々は、Ｙアドレス方向に移動し、メモリセル領域１００においてＸアドレス方向に存在する不良セル（例えば符号Ｒ１１のライン上の不良セル）を同時救済する能力がある。このように、Ｙアドレス方向を移動範囲とし、Ｘアドレス方向に存在する不良セルの同時救済能力を有するスペアラインの集合を、スペアライングループＹＳＬＧと呼ぶ。
【０００６】
メモリセル領域１００内における不良セルの分布（フェイル分布）が図９に示す通りであるとすると、符号Ｒ１１のライン上に配列されたメモリセルをスペアライングループＹＳＬＧの中の１本のスペアラインで置換すると共に、符号Ｃ１１、Ｃ１２、Ｃ１３のライン上に配列されたメモリセルをスペアライングループＸＳＬＧの中の３本のスペアラインで置換することにより、メモリデバイスの不良を救済することができる。なお、以下では、符号Ｃ１１、Ｃ１２、Ｃ１３、Ｒ１１のように、フェイルが存在するラインをフェイルラインと呼ぶ。
【０００７】
上記のように、メモリセル領域１００におけるフェイル分布（つまりフェイルライン）に対するスペアラインの最適な割当パターンを演算によって求めることをリダンダンシ演算という。従来のリダンダンシ演算では、フェイル数の多いフェイルラインから優先的にスペアラインを割当てる方法や、下記特許文献１に記載されているように、スペアライングループ毎にスペアラインの１本当たりのコストを求め、このスペアラインの１本当たりのコストから算出される救済効率を基にスペアラインの割当てを行う方法などが考案されている。
【０００８】
特許文献１の技術について具体的に説明すると、あるスペアライングループのリペア候補ラインの本数及び各リペア候補ライン上の未救済フェイル数を基に、そのスペアライングループの全体コストを算出し、当該全体コストをスペアライングループに属するスペアラインの本数で除算することにより、スペアラインの１本当たりのコストを算出する。ここで、リペア候補ラインとは、１本のスペアラインについて、フェイル上に割当て可能なライン（フェイルライン）の候補を指す（但し、同じスペアライングループに属するスペアラインは区別しない）。例えば、図９におけるスペアライングループＸＳＬＧに属するスペアラインのリペア候補ラインは、符号Ｃ１１、Ｃ１２、Ｃ１３、Ｃ１４、Ｃ１５のラインとなる。また、スペアライングループＹＳＬＧに属するスペアラインのリペア候補ラインは、符号Ｒ１１、Ｒ１２、Ｒ１３、Ｒ１４、Ｒ１５のラインとなる。
【０００９】
そして、１フェイル当たりの救済コストＣＲを、ＣＲ＝（スペアライン１本当たりのコスト）／（救済フェイル数）によって算出し、当該救済コストＣＲの逆数を救済効率（＝１／ＣＲ）とする。このようなコスト計算により、救済効率の高いリペア候補ラインを探索し、救済効率の高いリペア候補ラインに優先的にスペアラインの割当てを行い、全フェイル救済完了と判定されるまで、または救済不可能と判定されるまで、スペアラインの割当てを繰り返す。ここで、全フェイル救済完了と判定された場合、最終的に得られたスペアラインの割当パターンデータを用いて、実際のリダンダンシ処理（レーザトリマ）を行う。一方、全フェイルの救済は不可能と判定された場合、スペアラインの割当パターンを変更してリトライを行い、再度、全フェイル救済完了と判定されるまで、または救済不可能と判定されるまで、スペアラインの割当てを繰り返す。ここで、リトライ回数やリダンダンシ演算に要する時間が所定の閾値に到達した場合、最終的に救済不能デバイスと判断し、次のメモリデバイスのリダンダンシ演算を開始する。
【特許文献１】特開２００７−０６６３４９号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
ところで、近年においては、メモリデバイスの低価格化が進んでおり、試験に要するコストを含めたメモリデバイスの製造コストの低減が要求されている。このため、メモリ試験装置を用いた試験時間及びメモリデバイスの不良救済に要する時間（つまりリダンダンシ演算に要する時間）等を極力短縮する必要がある。上述したメモリデバイスの不良救済は製造歩留まりを向上させて製造コストを低減する上で必要不可欠なものであり、メモリデバイスの不良救済を行う場合には救済が可能であるメモリデバイスのみが全数救済されるというのが理想的である。
【００１１】
しかしながら、従来のリダンダンシ演算では、上述したように、救済効率の高いリペア候補ラインに優先的にスペアラインの割当てを行うため、最終的に全フェイル救済完了となるのか、または救済不可能となるのかはスペアラインの割当てが終了するまでわからなかった。このため、フェイル分布やデバイス構造（スペアラインの配置構造）によっては、リトライ回数が増大すると共にリダンダンシ演算に要する時間が増大し、本来ならば救済可能であったメモリデバイスを救済不能デバイスと判断して廃棄してしまうという問題があった。つまりメモリデバイスの救済率の低下を招いていた。
【００１２】
近年、メモリデバイスの大容量化に伴い、デバイス構造、つまりスペアラインの配置構造はますます複雑化しており、上述した従来のリダンダンシ演算では、このような複雑な構造を有するメモリデバイスに対応することは困難となっていた。
【００１３】
本発明は、このような事情に鑑みてなされたものであり、メモリデバイスの構造に依存しない汎用性を備えると共にリダンダンシ演算の高速化を図り、メモリデバイスの救済率の向上を図ることのできるリダンダンシ演算装置及びリダンダンシ演算方法並びにメモリ試験装置を提供することを目的とする。
【課題を解決するための手段】
【００１４】
上記課題を解決するために、本発明では、リダンダンシ演算装置に係る第１の解決手段として、複数のメモリセルが行アドレス方向及び列アドレス方向に２次元配列されたメモリセル領域の周辺に、複数の予備セルからなるスペアラインが設けられたメモリデバイスの不良救済を行う上で、前記メモリセル領域におけるフェイル分布に対する前記スペアラインの割当パターンを演算によって求めるリダンダンシ演算装置であって、全てのフェイルが救済されるための条件を第１の制約条件とし、同一の救済能力を有するスペアラインの集合であるスペアライングループ毎に使用されるスペアラインの本数を制限するための条件を第２の制約条件とし、フェイルの救済に使用されるスペアラインの総数、またはスペアラインをフェイルの救済に使用した場合に発生する総コストを目的関数とし、前記第１及び第２の制約条件の下、前記目的関数を最小化するという最適化問題を０−１整数計画法を適用して解くことにより、前記メモリセル領域におけるフェイル分布に対する前記スペアラインの割当パターンを求める演算処理部を備える、ことを特徴とする。
【００１５】
また、本発明では、リダンダンシ演算装置に係る第２の解決手段として、上記第１の解決手段において、前記演算処理部は、１本のスペアラインについて、前記メモリセル領域におけるフェイル上に割当可能なラインの候補をリペア候補ラインｊ（ｊ＝１、２、・・・、ｎ）とし、リペア候補ラインｊがフェイルｉ（ｉ＝１、２、・・・、Ｍ）を救済する場合を「１」、救済しない場合を「０」とする係数ｒｉｊと、リペア候補ラインｊがスペアライングループｋ（ｋ＝１、２、・・・、Ｋ）に属する場合を「１」、属さない場合を「０」とする係数ｇｋｊと、リペア候補ラインｊを採用する場合を「１」、採用しない場合を「０」とする変数ｘｊとを定義し、前記係数ｒｉｊと変数ｘｊとから成る下記（１５）式を、全てのフェイルが救済されるための第１の制約条件とし、前記係数ｇｋｊと変数ｘｊとから成る下記（１８）式を、スペアライングループｋ毎に使用されるスペアラインの本数を制限するための第２の制約条件とし、スペアライングループｋによって定まるコストｗｋと前記係数ｇｋｊと前記変数ｘｊとから成る下記（２０）式で表される総コストｚを目的関数とし、前記第１及び第２の制約条件の下、前記目的関数ｚを最小化するという最適化問題を０−１整数計画法を適用して解くことにより、ｘｊの最適解を求める、ことを特徴とする。
【００１６】
【数１】
【００１７】
また、本発明では、リダンダンシ演算装置に係る第３の解決手段として、上記第２の解決手段において、前記演算処理部は、下記（２１）式で表される行列Ａ、ｂ、ｘ、ｃを作成し、前記目的関数ｚを下記（２２）式で置き換え、前記第１及び第２の制約条件を下記（２３）式で置き換えることを特徴とする。
【００１８】
【数２】
【００１９】
また、本発明では、リダンダンシ演算装置に係る第４の解決手段として、上記第２または第３の解決手段において、前記メモリデバイスにおける前記スペアライングループの配置構造に応じた演算条件データを予め記憶する演算条件データ記憶部と、前記メモリセル領域におけるフェイルのアドレスを示すフェイルアドレスデータを記憶するフェイルアドレス記憶部と、を備え、前記演算処理部は、前記演算条件データ及び前記フェイルアドレスデータを基に、リペア候補ラインｊがフェイルｉを救済するか否かを判別することにより、前記係数ｒｉｊを作成することを特徴とする。
【００２０】
また、本発明では、リダンダンシ演算装置に係る第５の解決手段として、上記第４の解決手段において、前記演算条件データは、前記スペアライングループの救済領域であるメモリセル領域の原点位置を規定するベースアドレスデータと、スペアライングループの行アドレス方向及び列アドレス方向の幅を規定するマスクデータと、スペアライングループの救済可能範囲を規定するリペアマスクデータとで構成されることを特徴とする。
【００２１】
また、本発明では、リダンダンシ演算装置に係る第６の解決手段として、上記第５の解決手段において、前記演算処理部は、前記演算条件データの内、前記マスクデータと前記リペアマスクデータとの論理和をとった結果のビット反転データを判定用マスクデータとし、当該判定用マスクデータと前記フェイルアドレスデータとの論理和をとった結果が、前記ベースアドレスデータと一致した場合に、リペア候補ラインｊがフェイルｉを救済すると判別することを特徴とする。
【００２２】
また、本発明では、リダンダンシ演算装置に係る第７の解決手段として、上記第１〜第６のいずれかの解決手段において、前記０−１整数計画法の解法として、間接列挙法を適用した分枝限定法を用いることを特徴とする。
【００２３】
一方、本発明では、リダンダンシ演算方法に係る解決手段として、複数のメモリセルが行アドレス方向及び列アドレス方向に２次元配列されたメモリセル領域の周辺に、複数の予備セルからなるスペアラインが設けられたメモリデバイスの不良救済を行う上で、前記メモリセル領域におけるフェイル分布に対する前記スペアラインの割当パターンを演算によって求めるリダンダンシ演算方法であって、全てのフェイルが救済されるための条件を第１の制約条件とし、同一の救済能力を有するスペアラインの集合であるスペアライングループ毎に使用されるスペアラインの本数を制限するための条件を第２の制約条件とし、フェイルの救済に使用されるスペアラインの総数、またはスペアラインをフェイルの救済に使用した場合に発生する総コストを目的関数とし、前記第１及び第２の制約条件の下、前記目的関数を最小化するという最適化問題を０−１整数計画法を適用して解くことにより、前記メモリセル領域におけるフェイル分布に対する前記スペアラインの割当パターンを求める、ことを特徴とする。
【００２４】
さらに、本発明では、メモリ試験装置に係る解決手段として、メモリデバイスのパス／フェイルを示すフェイル情報を格納するフェイルメモリを有するメモリ試験装置であって、前記フェイルメモリに格納された前記フェイル情報を用いて、前記メモリデバイスのメモリセル領域におけるフェイル分布に対する前記スペアラインの割当パターンを演算によって求める請求項１〜請求項７のいずれか一項に記載のリダンダンシ演算装置を備えることを特徴とする。
【発明の効果】
【００２５】
本発明に係るリダンダンシ演算装置は、全てのフェイルが救済されるための条件を第１の制約条件とし、同一の救済能力を有するスペアラインの集合であるスペアライングループ毎に使用されるスペアラインの本数を制限するための条件を第２の制約条件とし、フェイルの救済に使用されるスペアラインの総数、またはスペアラインをフェイルの救済に使用した場合に発生する総コストを目的関数とし、前記第１及び第２の制約条件の下、前記目的関数を最小化するという最適化問題を０−１整数計画法を適用して解くことにより、メモリセル領域におけるフェイル分布に対するスペアラインの割当パターンを求めるものである。
【００２６】
すなわち、従来のリダンダンシ演算では、救済効率の高いリペア候補ラインに優先的にスペアラインの割当てを行うため、最終的に全フェイル救済完了となるのか、または救済不可能となるのかはスペアラインの割当てが終了するまでわからなかったが、本発明では、リダンダンシ演算の始めから全てのフェイルが救済されるための制約条件を考慮して、目的関数を最小化するという最適化問題を解くため、得られた最適解は必ず全フェイルの救済を満足していることになる。従って、本発明に係るリダンダンシ演算装置によれば、従来では必要であったリトライが不要となるので、メモリデバイスの構造に依存しない汎用性を備えることができると共に、リダンダンシ演算の高速化を図ることが可能であり、その結果、メモリデバイスの救済率の向上を図ることが可能である。
【発明を実施するための最良の形態】
【００２７】
以下、図面を参照して、本発明の一実施形態について説明する。
図１は、本発明の一実施形態におけるリダンダンシ演算装置を備えるメモリ試験装置の要部構成を示すブロック図である。図１に示す通り、メモリ試験装置１０は、試験パターン発生部１１、アドレス変換部１２、コンパレータ１３、フェイルメモリコントローラ１４、フェイルメモリ１５及びリダンダンシ演算装置２０を備えており、複数（例えば、数百個）のメモリデバイス３０の試験を並列して行う。なお、メモリデバイス３０は、Ｘアドレス（列アドレス）及びＹアドレス（行アドレス）により個々が特定される複数のメモリセルが２次元配列されたメモリセル領域と、メモリセル領域の周囲に、ライン状に形成された複数の予備セルからなるスペアラインを有する。なお、詳細は後述するが、メモリデバイス３０内のアドレスは、上記のＸアドレス及びＹアドレスの他、ページという要素も含めた３次元の要素によって定義されている。
【００２８】
試験パターン発生部１１は、メモリデバイス３０に与える試験パターンＤ１及び二次元のアドレスＡ１並びにパス／フェイル判定時に用いる期待値Ｄ３を発生する。アドレス変換部１２は、所定の変換規則に従って、試験パターン発生部１１で発生した二次元のアドレスＡ１を一次元のアドレスＡ２に変換する。コンパレータ１３は、メモリデバイス３０から読み出されたデータＤ２と試験パターン発生部１１から出力される期待値Ｄ３とを比較してパス／フェイルを示すフェイルデータＦＤを出力する。フェイルメモリコントローラ１４は、フェイルメモリ１５に対するフェイルデータＦＤの書き込み制御及び読み出し制御を行う。フェイルメモリ１５は、複数のメモリデバイス３０の試験結果を示すフェイルデータＦＤを記憶するものであり、その容量は例えば数百ギガビット程度である。
【００２９】
リダンダンシ演算装置２０は、フェイルが発生したメモリデバイス３０のメモリセル領域におけるフェイル分布（つまりフェイルライン）に対するスペアラインの最適な割当パターンを、０−１整数計画法を用いたリダンダンシ演算によって求めるものであり、演算処理部２１、演算条件データ記憶部２２、フェイルアドレス記憶部２３及び表示部２４を備えている。
【００３０】
演算処理部２１は、フェイルメモリコントローラ１４を介してフェイルメモリ１５からフェイルデータＦＤを取得すると共に、当該フェイルデータＦＤからフェイルが発生したメモリセルのアドレス（以下、フェイルアドレスと称す）を抽出し、このフェイルアドレスを所定のデータ表現形式のフェイルアドレスデータに変換してフェイルアドレス記憶部２３に記憶する。また、この演算処理部２１は、演算条件データ記憶部２２に記憶されている演算条件データと、フェイルアドレス記憶部２３に記憶されているフェイルアドレスデータとに基づいて、フェイルが発生したメモリデバイス３０のメモリセル領域におけるフェイルラインに対するスペアラインの最適な割当パターンを、０−１整数計画法を用いたリダンダンシ演算によって求める。なお、この演算処理部２１による０−１整数計画法を用いたリダンダンシ演算についての詳細は後述する。
【００３１】
演算条件データ記憶部２２は、ＤＵＴ３０に設けられたスペアラインの配置構造を規定する演算条件データを予め記憶しており、上記演算処理部２１の制御の下、演算条件データを演算処理部２１に出力する。フェイルアドレス記憶部２３は、上記演算処理部２１の制御の下、上記フェイルアドレスデータを記憶する一方、要求に応じてフェイルアドレスデータを演算処理部２１に出力する。表示部２４は、例えば液晶ディスプレイであり、演算処理部２１の制御の下、リダンダンシ演算の演算結果を表示する。
【００３２】
以下、上記の演算条件データ及びフェイルアドレスデータについて詳細に説明する。図２は、メモリデバイス３０におけるメモリセル領域及びスペアラインの配置構造を示す概念図である。図２に示すように、メモリセル領域はブロック単位（ＢＬＫ１、ＢＬＫ２、ＢＬＫ３）に区分されており、それぞれのブロックは独立して動作し、互いに影響を及ぼさない。本実施形態におけるリダンダンシ演算装置２０（演算処理部２１）は、このブロック毎にリダンダンシ演算を行う。
【００３３】
また、図２に示すように、１つのブロック内には、予備セル領域であるスペアラインが形成されており、以下では、同一の救済能力を有するスペアラインの集合をスペアライングループ（ＸＳＬＧ１、ＸＳＬＧ２、ＹＳＬＧ）と呼ぶ。本実施形態では、これらスペアライングループの救済メモリセル領域を、セグメント（ＳＥＧ１、ＳＥＧ２）という領域で定義する。つまり、図２の例では、スペアライングループＸＳＬＧ１に属するスペアラインは、Ｘアドレス方向を移動範囲とし、セグメントＳＥＧ１のＹアドレス方向に存在する不良セル（以下、フェイルと略す）の同時救済能力を有する。また、スペアライングループＸＳＬＧ２に属するスペアラインは、Ｘアドレス方向を移動範囲とし、セグメントＳＥＧ２のＹアドレス方向に存在するフェイルの同時救済能力を有する。また、スペアライングループＹＳＬＧに属するスペアラインは、Ｙアドレス方向を移動範囲とし、セグメントＳＥＧ１及びＳＥＧ２のＸアドレス方向に存在するフェイルの同時救済能力を有する。
【００３４】
本実施形態では、上記のような構造のメモリデバイス３０内の位置を指定するためのアドレスを、Ｘアドレス及びＹアドレスに、ページＰを加えた３次元要素（Ｐ、Ｘ、Ｙ）によって定義する。メモリデバイス３０がページ構造を有しないデバイスである場合、ページＰ＝０とすれば良い。このような３次元要素からなるアドレスを用いることによって、セグメントやスペアライングループ、フェイルの位置などを定義することができる。
【００３５】
本実施形態では、スペアライングループを、ベースアドレスデータ、マスクデータ、リペアマスクデータの３つのデータによって定義する。ベースアドレスデータとは、スペアライングループの救済領域であるセグメントの原点位置を規定するデータである。マスクデータとは、スペアライングループによって同時救済可能な領域、つまりスペアライングループのＸアドレス方向及びＹアドレス方向の幅を規定するデータである。リペアマスクデータとは、スペアライングループの移動可能範囲（救済可能範囲）を規定するデータである。本実施形態では、これら３つのデータを１組の演算条件データとする。この演算条件データは、スペアライングループの配置構造によって変わるため、メモリデバイス３０におけるスペアライングループの配置構造に応じて演算条件データを作成し、演算条件データ記憶部２２に予め記憶しておく。
【００３６】
図３及び図４は、所定のスペアライングループの配置構造に対応する演算条件データの一例を示したものである。図３（ａ）は、Ｘアドレス方向を移動範囲とし、セグメントＳＥＧ１のＹアドレス方向に存在するフェイルの同時救済能力を有するスペアライングループＸＳＬＧ１の演算条件データである。ここで、Ｘアドレス「０」〜「ＦＦ」（１６進数）、Ｙアドレス「０」〜「ＦＦ」で定義される領域をセグメントＳＥＧ１とする。つまり、セグメントＳＥＧ１はＸアドレス方向及びＹアドレス方向に「１００（＝２５６＝２８）」の幅を有している。
【００３７】
演算条件データ（ベースアドレスデータ、マスクデータ、リペアマスクデータ）は、ページＰに対応するページビット領域ＰＢと、Ｙアドレスに対応するＹアドレスビット領域ＹＢと、Ｘアドレスに対応するＸアドレスビット領域ＸＢとで構成されている。ページビット領域ＰＢのビット数はメモリデバイス３０が有するページ数に応じて設定すれば良いが、Ｙアドレスビット領域ＹＢ及びＸアドレスビット領域ＸＢでは、少なくとも１つのセグメントに対応可能なビット数（つまり８ビット）が必要である。なお、図３及び図４において、ページビット領域ＰＢ、Ｙアドレスビット領域ＹＢ、Ｘアドレスビット領域ＸＢの斜線部分はビットが「１」にセットされていることを示し、白抜き部分はビットが「０」にセットされていることを示している。
【００３８】
図３（ａ）に示すように、セグメントＳＥＧ１を救済するスペアライングループＸＳＬＧ１のベースアドレスデータは救済領域（セグメントＳＥＧ１）の原点を規定するデータであるので、Ｙアドレスビット領域ＹＢ及びＸアドレスビット領域ＸＢの全ビットは「０」（１６進数で「０」）にセットされる。また、マスクデータはスペアライングループＸＳＬＧ１によって同時救済可能な領域を規定するデータなので、Ｙアドレスビット領域ＹＢの８ビット分は「１」（１６進数で「ＦＦ」）にセットされ、Ｘアドレスビット領域ＸＢの全ビットは「０」にセットされる。つまり、このマスクデータによって、スペアライングループＸＳＬＧ１は、セグメントＳＥＧ１内のＹアドレス方向に対して１ライン上に存在するフェイルを同時救済可能であることを定義している。また、リペアマスクデータはスペアライングループＸＳＬＧ１の移動可能範囲を規定するデータなので、Ｘアドレスビット領域ＸＢの８ビット分は「１」（１６進数で「ＦＦ」）にセットされ、Ｙアドレスビット領域ＹＢの全ビットは「０」にセットされる。つまり、このリペアマスクデータによって、スペアライングループＸＳＬＧ１は、セグメントＳＥＧ１内のＸアドレス方向に移動可能であることを定義している。
【００３９】
図３（ｂ）は、Ｙアドレス方向を移動範囲とし、セグメントＳＥＧ１のＸアドレス方向に存在するフェイルの同時救済能力を有するスペアライングループＹＳＬＧ１の演算条件データである。この図に示すように、スペアライングループＹＳＬＧ１のベースアドレスデータにおいて、Ｙアドレスビット領域ＹＢ及びＸアドレスビット領域ＸＢの全ビットは「０」（１６進数で「０」）にセットされる。また、マスクデータにおいて、Ｘアドレスビット領域ＸＢの８ビット分は「１」（１６進数で「ＦＦ」）にセットされ、Ｙアドレスビット領域ＹＢの全ビットは「０」にセットされる。また、リペアマスクデータにおいて、Ｙアドレスビット領域ＹＢの８ビット分は「１」（１６進数で「ＦＦ」）にセットされ、Ｘアドレスビット領域ＸＢの全ビットは「０」にセットされる。
【００４０】
図４（ａ）は、Ｙアドレス方向を移動範囲とし、セグメントＳＥＧ１及びＳＥＧ２のＸアドレス方向に存在するフェイルの同時救済能力を有するスペアライングループＹＳＬＧ１−２の演算条件データである。なお、Ｘアドレス「１００」〜「１ＦＦ」（１６進数）、Ｙアドレス「０」〜「ＦＦ」で定義される領域をセグメントＳＥＧ２とする。この図に示すように、スペアライングループＹＳＬＧ１-２のベースアドレスデータにおいて、Ｙアドレスビット領域ＹＢ及びＸアドレスビット領域ＸＢの全ビットは「０」（１６進数で「０」）にセットされる。また、マスクデータにおいて、Ｘアドレスビット領域ＸＢの９ビット分は「１」（１６進数で「１ＦＦ」）にセットされ、Ｙアドレスビット領域ＹＢの全ビットは「０」にセットされる。また、リペアマスクデータにおいて、Ｙアドレスビット領域ＹＢの８ビット分は「１」（１６進数で「ＦＦ」）にセットされ、Ｘアドレスビット領域ＸＢの全ビットは「０」にセットされる。
【００４１】
図４（ｂ）は、Ｘアドレス方向を移動してセグメントＳＥＧ１を救済すると共に、連動してセグメントＳＥＧ２を同時救済する能力を有するスペアライングループＸＳＬＧ１＆２の演算条件データである。この図に示すように、スペアライングループＸＳＬＧ１＆２のベースアドレスデータにおいて、Ｙアドレスビット領域ＹＢ及びＸアドレスビット領域ＸＢの全ビットは「０」（１６進数で「０」）にセットされる。また、マスクデータにおいて、Ｘアドレスビット領域ＸＢの９ビット目は「１」（１６進数で「１００」）にセットされ、Ｙアドレスビット領域ＹＢの全ビットは「１」（１６進数で「ＦＦ」）にセットされる。また、リペアマスクデータにおいて、Ｘアドレスビット領域ＸＢの８ビット分は「１」（１６進数で「ＦＦ」）にセットされ、Ｙアドレスビット領域ＹＢの全ビットは「０」にセットされる。
【００４２】
このスペアライングループＸＳＬＧ１＆２の演算条件データは、以下のような作成方法を用いる。マスクデータを作成する場合、まず、図５に示すように、スペアライングループがセグメントＳＥＧ１を救済する場合のベースアドレスデータ（Ｙアドレスビット領域ＹＢ及びＸアドレスビット領域ＸＢの全ビット「０」）と、スペアライングループがセグメントＳＥＧ２を救済する場合のベースアドレスデータ（Ｘアドレスビット領域ＸＢの９ビット目「１」、Ｙアドレスビット領域ＹＢの全ビット「０」）との排他的論理和をとる。そして、その排他的論理和の結果と、スペアライングループがセグメントＳＥＧ１を救済する場合のマスクデータ（Ｙアドレスビット領域ＹＢの８ビット分は「１」、Ｘアドレスビット領域ＸＢの全ビット「０」）との論理和をとり、これにより得られたデータをスペアライングループＸＳＬＧ１＆２のマスクデータとして使用する。また、ベースアドレスデータ及びリペアマスクデータとしては、セグメントＳＥＧ１を救済する場合のベースアドレスデータ及びリペアマスクデータを使用する。
なお、図４（ａ）のようなスペアライングループＹＳＬＧ１-２の演算条件データを作成する場合も同様の手法を用いることができる。
【００４３】
図４（ｃ）は、Ｘアドレス方向を移動してセグメントＳＥＧ１またはＳＥＧ２の一方を救済する能力を有するスペアライングループＸＳＬＧ１｜２の演算条件データである。この図に示すように、スペアライングループＸＳＬＧ１｜２のベースアドレスデータにおいて、Ｙアドレスビット領域ＹＢ及びＸアドレスビット領域ＸＢの全ビットは「０」（１６進数で「０」）にセットされる。また、マスクデータにおいて、Ｙアドレスビット領域ＹＢの８ビット分は「１」（１６進数で「ＦＦ」）にセットされ、Ｘアドレスビット領域ＸＢの全ビットは「０」にセットされる。また、リペアマスクデータにおいて、Ｘアドレスビット領域ＸＢの９ビット分は「１」（１６進数で「１ＦＦ」）にセットされ、Ｙアドレスビット領域ＹＢの全ビットは「０」にセットされる。
【００４４】
このスペアライングループＸＳＬＧ１｜２の演算条件データは、以下のような作成方法を用いる。リペアマスクデータを作成する場合、まず、スペアライングループがセグメントＳＥＧ１を救済する場合のベースアドレスデータと、スペアライングループがセグメントＳＥＧ２を救済する場合のベースアドレスデータとの排他的論理和をとる。そして、その排他的論理和の結果と、スペアライングループがセグメントＳＥＧ１を救済する場合のリペアマスクデータとの論理和をとり、これにより得られたデータをスペアライングループＸＳＬＧ１｜２のリペアマスクデータとして使用する。また、ベースアドレスデータ及びマスクデータとしては、セグメントＳＥＧ１を救済する場合のベースアドレスデータ及びマスクデータを使用する。
【００４５】
以上説明したような救済能力を有するスペアライングループがメモリデバイス３０内のメモリセル領域（セグメント）に応じて複数設けられており、各スペアライングループに応じた演算条件データが演算条件データ記憶部２２に予め記憶されている。
なお、フェイルアドレス記憶部２２に記憶されるフェイルアドレスデータも演算条件データと同様に、ページビット領域ＰＢ、Ｙアドレスビット領域ＹＢ、Ｘアドレスビット領域ＸＢから構成されている。つまり、演算処理部２１は、フェイルメモリコントローラ１４を介してフェイルメモリ１５からフェイルデータＦＤを取得すると共に、当該フェイルデータＦＤからフェイルアドレスを抽出し、このフェイルアドレスを上記のように、ページビット領域ＰＢ、Ｙアドレスビット領域ＹＢ、Ｘアドレスビット領域ＸＢから構成されるフェイルアドレスデータに変換してフェイルアドレス記憶部２３に記憶する。
【００４６】
次に、上記のように構成されたメモリ試験装置１０の動作について説明する。
メモリ試験装置１０は、まずメモリデバイス３０の試験を行い、次いで、フェイルが発生したメモリデバイス３０のメモリセル領域（セグメント）におけるフェイル分布に対するスペアラインの最適な割当パターンを、０−１整数計画法を用いたリダンダンシ演算によって求める。
【００４７】
メモリデバイス３０の試験が開始されると、まず試験パターン発生部１１から試験パターンＤ１とアドレスＡ１とが出力されて、試験パターンＤ１がメモリデバイス３０に書き込まれる。試験パターンＤ１の書き込みが終了すると、試験パターン発生部１１からアドレスＡ１と期待値Ｄ３とが出力される。
【００４８】
試験パターン発生部１１から出力されたアドレスＡ１がメモリデバイス３０に与えられると、メモリデバイス３０に予め書き込んだ試験パターンがデータＤ２として読み出されてコンパレータ１３に入力され、試験パターン発生部１１から出力された期待値Ｄ３と比較されてパス／フェイルが判定され、パス／フェイルを示すフェイルデータＦＤがフェイルメモリコントローラ１４に入力される。また、試験パターン発生部１１から出力されたアドレスＡ１は、アドレス変換部１２に出力されて一次元のアドレスＡ２に変換されフェイルメモリコントローラ１４に入力される。フェイルメモリコントローラ１４は、アドレスＡ２で示されるフェイルメモリ１５の記憶領域に、コンパレータ１３から出力されたフェイルデータＦＤを書き込む。試験パターン発生部１１からアドレスＡ１及び期待値Ｄ３が出力される度に上記の動作が繰り返し行われ、これによりフェイルデータＦＤがフェイルメモリ１５に順次記憶される。
【００４９】
メモリデバイス３０の試験が終了すると、リダンダンシ演算装置２０の演算処理部２１は、フェイルメモリコントローラ１４を制御してフェイルメモリ１５に記憶されたフェイルデータＦＤを読み出すと共に、フェイルデータＦＤからフェイルアドレスを抽出し、このフェイルアドレスをページビット領域ＰＢ、Ｙアドレスビット領域ＹＢ、Ｘアドレスビット領域ＸＢから構成されるフェイルアドレスデータに変換してフェイルアドレス記憶部２３に記憶する。演算処理部２１は、フェイルアドレス記憶部２３へのフェイルアドレスデータの記憶処理が完了すると、以下に説明するリダンダンシ演算を行う。
【００５０】
まず、本実施形態における０−１整数計画法を用いたリダンダンシ演算の原理について説明する。
【００５１】
＜０−１整数計画法＞
０−１整数計画法とは、変数ｘｊ及び係数ｃｊから成る（１）式で表される一次関数を目的関数ｚとし、変数ｘｊ、係数ａｉｊ及び係数ｂｊから成る（２）式で表される一次不等式の制約条件と、変数ｘｊが「０」または「１」の値しか取らないという（３）式で表される制約条件の下で、上記目的関数ｚを最小化または最大化するという最適化問題を解くことをいう。
【００５２】
【数３】
【００５３】
上記（１）、（２）、（３）式で表される０−１整数計画法の解の個数は２ｎ個である。よって、それらを全て列挙して逐一実行可能であるか否かを確認し、実行可能であれば、その目的関数ｚを求めることによってこの最適化問題を解くことができることは明らかである。しかしながら、変数ｘｊの個数ｎの値が大きくなると解の個数は指数関数的に増大するため、上記のように解の全てを列挙する方法を用いると演算時間が膨大となる恐れがある。そこで、このような０−１整数計画法の解法として、間接列挙法を適用した分枝限定法を用いる。この間接列挙法は変数の０−１条件を積極的に利用した解法である。
【００５４】
＜分枝限定法、間接列挙法＞
直接的な解法が見つかっていない最適化問題Ｐ０が与えられている場合、（４）式に示すように、適当な条件を設定して、Ｐ０の実行可能領域Ｘ０をいくつかの部分領域Ｘ１、Ｘ２、・・・Ｘｋに分割し、その各々に対応する問題Ｐｋを考え、これをＰ０の子問題という。この一群の子問題Ｐｋ（ｋ＝１、２、・・・）を解いて得られた解の中でｆ（ｘ）の値が最小のものを見つければ、問題Ｐ０の最適解が得られることは明らかである。この子問題Ｐ０がまだ直接解けない場合は、Ｘｋをさらにいくつかの領域に分け、Ｐｋをさらにいくつかの子問題に分解する。このような手順を繰り返すことで、元の問題Ｐ０を解く方法が分枝限定法である。
【００５５】
【数４】
【００５６】
この分枝限定法は、分枝操作と限定操作とで構成されている。分枝操作とは、問題Ｐｋが直接解けない場合、その実行可能領域となるＸｋを（５）式で表されるいくつかの部分集合Ｘｐ、・・・、Ｘｑに分割し、Ｐｋをその一群の子問題である（６）式で置き換えることである。
【００５７】
【数５】
【００５８】
一般に、Ｐｋの実行可能領域Ｘｋは、Ｘ０に制限を加えたＸｋ＝Ｘ０∩Ｂｋという形で与えられている。ここで、（７）式で表されるＢｋ，ｐ、・・・、Ｂｋ，ｑを用いて、Ｘｌを（８）式とすることにより、（５）式を満たす分割が得られる。
【００５９】
【数６】
【００６０】
上記のような子問題への分枝操作を終端させる操作を限定操作という。この限定操作では、（４）式の制約条件をさらに緩めた緩和問題Ｐｋ’を解くことになる。
【００６１】
【数７】
【００６２】
ここで、問題Ｐｋと緩和問題Ｐｋ’の間には次の関係が成立する。
(i)Ｐｋ’が実行可能解を持たない時は、Ｐｋも実行可能解を持たない。
(ii)Ｐｋ’の最適解をｘ’としたとき、ｘ’∈Ｘｋならばｘ’はＰｋの最適解である。
(iii)Ｐｋ’の最適値をｚ’とし、Ｐｋの最適値をｚ＊とすると、ｚ’＜ｚ＊である。
【００６３】
問題Ｐ０の少なくとも１つの実行可能解ｘ”が得られているとし、ｘ”に対応する目的関数値をｚ”＝ｆ’（ｘ”）とすると、ｚ”はＰ０の暫定的な最適値となる。従って、Ｐｋ’の最適値ｚｋ’が下記（１０）式を満たせば、問題Ｐｋのいかなる実行可能解もｘ”より良い目的関数値を与えないことが明らかである。よって、この場合、Ｐｋをこれ以上分枝することは無意味であり、このような場合、Ｐｋは限定操作によって見切られて分枝停止となる。さらに、Ｐｋ’の最適解ｘｋ’が下記（１１）式を満たす場合、ｘｋ’はＰｋの最適解となる。よって、この場合もＰｋを分枝する必要はない。
【００６４】
【数８】
【００６５】
このように（１０）式または（１１）式が成立するか否かを調べることを子問題Ｐｋを探査するといい、（１０）式または（１１）式が成立したことが判明した場合、子問題Ｐｋは探査済みとなり、それ以上分枝しても無意味なので、この時点で子問題Ｐｋは分枝停止となる。分枝限定法とは、上記のような分枝操作と限定操作を繰り返すことによって、元の問題Ｐ０を解くものである。
【００６６】
また、上記（８）式において、Ｂｋ，ｌとして、下記（１２）式を用いることにより、列挙する解の個数を減らすことができる。このように、０−１条件を利用して列挙する解の個数を減らし、効率良く問題を解く方法が間接列挙法である。
【００６７】
【数９】
【００６８】
＜０−１整数計画法を用いたリダンダンシ演算＞
次に、上記のような０−１整数計画法の原理を応用した、本実施形態におけるリダンダンシ演算について説明する。
まず、リペア候補ライン（１本のスペアラインについて、フェイル上に割当て可能なライン（フェイルライン）の候補）を数え上げて、通し番号ｊ＝１、２、・・・、ｎで表す（但し、同じスペアライングループに属するスペアラインは区別しない）。また、フェイルを通し番号ｉ＝１、２、・・・、Ｍで表し、スペアライングループを通し番号ｋ＝１、２、・・・、Ｋで表す。なお、計算量を減らすために、フェイルを救済しないスペアライングループは除外しておく。
【００６９】
ここで、係数ｒｉｊと変数ｘｊを、下記（１３）及び（１４）式のように定義すると、全てのフェイルが救済されるための条件は、下記（１５）式で表される。また、どのリペア候補ラインも少なくとも１つはフェイルを救済するため、付帯条件として下記（１６）式が成立する。
【００７０】
【数１０】
【００７１】
また、スペアライングループｋに属するスペアラインの本数をＬｋとし、係数ｇｋｊを下記（１７）式のように定義すると、スペアライングループｋ毎に使用されるスペアラインの本数を制限するための条件は、下記（１８）式で表すことができる。また、どのリペア候補ラインも属するスペアライングループの数は１つであるから、付帯条件として下記（１９）式が成立する。
【００７２】
【数１１】
【００７３】
ここで、スペアラインを使用すると、属するスペアライングループｋによって定まるコストｗｋが発生する場合がある。この時の総コストｚは、下記（２０）で表すことができる。
【００７４】
【数１２】
【００７５】
全てのフェイルを救済して、総コストｚを最小化するという最適化問題を考えると、以下に示すように、（１５）式を第１の制約条件、（１８）式を第２の制約条件とし、上記（２０）式を目的関数とした、０−１整数計画問題として定式化される。
【００７６】
【数１３】
【００７７】
ここで、下記（２１）式に示すような、行列Ａ、ｂ、ｘ、ｃを定義すると、目的関数及び制約条件は、下記（２２）、（２３）式のように表すことができる。
【００７８】
【数１４】
【００７９】
このように、本実施形態におけるリダンダンシ演算では、上記（２３）式で表される制約条件の下、（２２）式で表される目的関数ｚを最小化するという最適化問題を解き、ｘｊの最適解を求めることにより、あるブロックのフェイル分布に対して、全フェイルを救済し且つ総コストｚを最小化することのできるスペアラインの割当パターンを求める。そして、リダンダンシ演算における０−１整数計画法の解法として、上述した間接列挙法を適用した分枝限定法を用いる。
【００８０】
具体的には、リダンダンシ演算における最適化問題の規模の縮小化については以下のように行う。あるフェイルｉ’に対して、リペア候補ラインがｊ’の１通りしかない場合、リペア候補ラインｊ’の採用が確定し、ｘｊ’＝１と定まる。この時、行列Ａの第ｊ’列と、行列ｘ、ｃの第ｊ’行は削除することができ、行列ｂは、ｂ−（Ａの第ｊ’列）、すなわち、下記（２４）式で置き換えることができる。
【００８１】
【数１５】
【００８２】
この結果、行列ｂｎｅｗの第ｉ’行の成分は、１−ｒｉ’ｊ’なので零となるが、その他にも第ｉ行（１＜ｉ＜Ｍ）が零ならば、フェイルｉも同時に救済されているので、このような行は全て行列Ａ、ｂｎｅｗから削除することができる。また、行列ｂｎｅｗの第Ｍ＋ｋ行（１＜ｋ＜Ｋ）が零ならば、スペアライングループｋのスペアラインは全て使い果たしているので、このような行を行列Ａ、ｂｎｅｗから削除する。スペアライングループｋに属するリペア候補ラインｊ（すなわち、ｇｋｊ＝１となるｊ）についてはｘｊ＝０と定まるので、行列Ａの第ｊ列と、行列ｘ、ｃの第ｊ行も削除することができる。このような操作を繰り返した結果、行列Ａの第ｉ行（１＜ｉ＜Ｍ）の成分が全て零となった場合、フェイルｉは救済不可能と判定される。
【００８３】
この他、最適化問題の規模を縮小する方法として、救済できるフェイル数が大きなリペア候補ラインｊの採用を確定する（ｘｊ＝１）という方法も考えられる。また、その他のヒューリスティックな方法によって採用するリペア候補ラインを確定していくと、同様に問題規模を縮小することができる。
【００８４】
以下、リダンダンシ演算装置２０の演算処理部２１によって実行されるリダンダンシ演算の処理手順について、図６のフローチャートを参照して説明する。
【００８５】
まず、演算処理部２１は、演算条件データ記憶部２２から演算条件データを読み込むと共に、フェイルアドレスデータ記憶部２３からフェイルアドレスデータを読み込む（ステップＳ１）。そして、演算処理部２１は、演算条件データの内、マスクデータとリペアマスクデータを用いて判定用マスクデータを作成する（ステップＳ２）。
【００８６】
ここで、判定用マスクデータとは、マスクデータとリペアマスクデータとの論理和をとり、その結果得られたデータにビット反転を施して得られるデータである。図７に、図３（ａ）のスペアライングループＸＳＬＧ１に対応する演算条件データから作成した判定用マスクデータを示す。この判定用マスクデータは、上記（１３）式で表される係数ｒｉｊを作成するため、つまり、あるリペア候補ラインｊが、あるフェイルｉを救済可能か否かを判別するために用いられるデータであり、判定用マスクデータとフェイルアドレスデータとの論理和をとることで得られたアドレスデータが、そのリペア候補ラインｊが属するスペアライングループのベースアドレスデータと一致する場合、そのリペア候補ラインｊはフェイルｉを救済可能であると判別することができる。
【００８７】
このように、演算処理部２１は、判定用マスクデータとフェイルアドレスデータとの論理和をとることで得られたアドレスデータが、そのリペア候補ラインｊが属するスペアライングループのベースアドレスデータと一致するか否かを判別することによって、そのリペア候補ラインｊはフェイルｉを救済可能であるか否かを判別して係数ｒｉｊを作成する他、上記（１７）式で表される係数ｇｉｊを作成して、（２１）式で表される各行列を作成する（ステップＳ３）。そして、演算処理部２１は、上述したような０−１整数計画法の解法として、間接列挙法を適用した分枝限定法を用いて、（２２）（２３）式で表される最適化問題を解き、ｘｊの最適解（以下、救済解と称す）を求めることにより、あるブロックのフェイル分布に対して、全フェイルを救済し且つ総コストｚを最小化することのできるスペアラインの割当パターンを求める（ステップＳ４）。
【００８８】
そして、演算処理部２１は、上記ステップＳ４における演算結果を表示部２４に表示させる（ステップＳ５）。具体的には、演算処理部２１は、救済解を求めることができればスペアラインの割当パターンを表示部２４に表示させ、救済解を求めることができなければ「救済不可能」というメッセージを表示部２４に表示させる。そして、演算処理部２１は、救済解を求めることができた場合、実際のリダンダンシ処理を行う（レーザトリマ等によってスペアラインとフェイルラインとの置換を行う）レーザリペア装置に、使用するスペアラインのアドレス（リペアアドレス）を通知する（ステップＳ６）。なお、このレーザリペア装置が、メモリ試験装置１０内に設けられていない場合、一旦、演算結果を所定の記憶部に記憶しておき、全てのメモリデバイス３０の試験とリダンダンシ演算が終了した後、上記記憶部に記憶されている演算結果を記憶媒体に格納して、レーザリペア装置に演算結果を移動させるようにしても良い。
【００８９】
本願発明者は、様々なフェイル分布やスペアライングループの配置構造を用いて、上述した本実施形態におけるリダンダンシ演算の検証を行い、例えば図８に示すような基本的なスペアライングループの配置構造では、フェイル数が多くてもリダンダンシ演算に要する時間は数ｍｓｅｃ程度であるという結果を得ることができ、また、救済不可能な条件でリダンダンシ演算を行った場合は、正確に救済不可能という演算結果を得ることができた。図８は、リダンダンシ演算の検証に用いたフェイル分布及びスペアライングループの配置構造の一例である。図８（ａ）は、スペアライングループＸＳＬＧ１及びＹＳＬＧ１の配置構造を示し、図８（ｂ）は、セグメントＳＥＧ１におけるフェイル分布（フェイルアドレス）を示し、図８（ｃ）は、本実施形態におけるリダンダンシ演算の結果として得られたスペアラインの割当パターンを示している。
さらに、従来のリダンダンシ演算では救済解を得ることができなかったフェイル分布及びスペアライングループの配置構造を用いて、本実施形態におけるリダンダンシ演算の検証を行った結果、数十ｍｓｅｃ程度の短時間で救済解を得ることができた。
【００９０】
以上説明したように、本実施形態におけるリダンダンシ演算装置２０では、全てのフェイルが救済されるための条件を第１の制約条件とし、同一の救済能力を有するスペアラインの集合であるスペアライングループ毎に使用されるスペアラインの本数を制限するための条件を第２の制約条件とし、スペアラインをフェイルの救済に使用した場合に発生する総コストを目的関数とし、上記第１及び第２の制約条件の下、上記目的関数（総コスト）を最小化するという最適化問題を０−１整数計画法を適用して解くことにより、メモリセル領域（セグメント）におけるフェイル分布に対するスペアラインの割当パターンを求める。
【００９１】
すなわち、従来のリダンダンシ演算では、救済効率の高いリペア候補ラインに優先的にスペアラインの割当てを行うため、最終的に全フェイル救済完了となるのか、または救済不可能となるのかはスペアラインの割当てが終了するまでわからなかったが、本実施形態におけるリダンダンシ演算では、演算の始めから（１５）式で表される全てのフェイルが救済されるための制約条件を考慮して、目的関数を最小化するという最適化問題を解くため、得られた救済解は必ず全フェイルの救済を満足していることになる。従って、本実施形態のリダンダンシ演算によれば、従来では必要であったリトライが不要となるので、メモリデバイスの構造に依存しない汎用性を備えることができると共に、リダンダンシ演算の高速化を図ることが可能であり、その結果、メモリデバイス３０の救済率の向上を図ることが可能である。
【００９２】
また、本実施形態のリダンダンシ演算では０−１整数計画法を用いるため、変数ｘｊは「１」または「０」の値しか取り得ず、リダンダンシ演算の高速化に寄与する。さらに、０−１整数計画法の解法として、間接列挙法を適用した分枝限定法を用いることにより、さらにリダンダンシ演算の高速化を図ることが可能である
【００９３】
なお、上記実施形態において、スペアラインをフェイルの救済に使用した場合に発生する総コストｚを目的関数としたが、これに限らず、フェイルの救済に使用されるスペアラインの総数を目的関数とし、この使用されるスペアラインの総数を最小化するという最適化問題を０−１整数計画法を適用して解くようにしても良い。この場合、（２０）式において、係数ｃｊを削除すれば良い。
【００９４】
また、上記実施形態では、メモリ試験装置１０内にリダンダンシ演算装置２０が設けられている場合を想定して説明したが、これに限らず、リダンダンシ演算装置２０を別個に設け、メモリ試験装置１０からフェイル情報を取得するような構成としても良い。
【図面の簡単な説明】
【００９５】
【図１】本発明の一実施形態に係るリダンダンシ演算装置２０を備えたメモリ試験装置１０の構成ブロック図である。
【図２】本発明の一実施形態に係るメモリデバイス３０の内部構造を示す概念図である。
【図３】本発明の一実施形態に係るリダンダンシ演算装置２０における演算条件データ記憶部２２に記憶されている演算条件データの第１の例である。
【図４】本発明の一実施形態に係るリダンダンシ演算装置２０における演算条件データ記憶部２２に記憶されている演算条件データの第２の例である。
【図５】演算条件データにおけるマスクデータの作成方法を示す説明図である。
【図６】本発明の一実施形態に係るリダンダンシ演算装置２０における演算処理部２１が実行するリダンダンシ演算のフローチャートである。
【図７】リダンダンシ演算で使用される判定用マスクデータの作成方法を示す説明図である。
【図８】本発明の一実施形態に係るリダンダンシ演算装置２０にて行われるリダンダンシ演算の検証例である。
【図９】リダンダンシ処理の説明図である。
【符号の説明】
【００９６】
１０…メモリ試験装置、１１…試験パターン発生部、１２…アドレス変換部、１３…コンパレータ、１４…フェイルメモリコントローラ、１５…フェイルメモリ、２０…リダンダンシ演算装置、２１…演算処理部、２２…演算条件データ記憶部、２３…フェイルアドレス記憶部、２４…表示部、３０…メモリデバイス
【技術分野】
【０００１】
本発明は、メモリデバイスにおける不良セルを予備セルで置換するリダンダンシ処理を行う上で、不良セルに対する予備セルの最適な割当パターンを演算によって求めるリダンダンシ演算装置及びリダンダンシ演算方法並びに当該装置を備えるメモリ試験装置に関する。
【背景技術】
【０００２】
ＲＡＭ（Random Access Memory）等のメモリデバイスは、製造時においてメモリセルに１つでも欠陥があると不良になる。このため、通常は、本来メモリセルとして用いられるセル領域の周囲に予備セルを形成しておき、メモリ試験装置の試験によってメモリデバイスに欠陥が生じた（フェイルと判定された）不良セルが検出された場合、レーザトリマ等によってメモリデバイス内の所定のパターンを切断して、不良セルを予備セルで置換して不良デバイスを救済することにより、製造歩留まりの低下を防止している。このように、メモリデバイスにおいて不良セルを予備セルで置換する処理をリダンダンシ処理という。
【０００３】
このような予備セルによる置換は、図９に示すように、ライン単位で行われることが一般的である。図９は、メモリデバイスに形成されるメモリセル及びその周囲に形成された予備セルを概念的に示す図である。図９において、符号１００を付した矩形領域は複数のメモリセルが２次元配列されたメモリセル領域を表しており、このメモリセル領域１００内の個々のメモリセルは列アドレス（Ｘアドレス）と行アドレス（Ｙアドレス）とによって特定される。メモリセル領域１００の内部に示した記号「×」は、メモリ試験装置の試験によってフェイルと判定された不良セルを表している。
【０００４】
図９に示す例では、メモリセル領域１００の図中右側に、Ｙアドレス方向に延在するスペアライン（ライン状にＹアドレスの数だけ形成された予備セルの集合体）が複数本用意されており、メモリセル領域１００の図中下側に、Ｘアドレス方向に延在するスペアライン（ライン状にＸアドレスの数だけ形成された予備セルの集合体）が複数本用意されている。ここで、同一の救済能力を有するスペアラインの集合をスペアライングループという。
【０００５】
例えば、図９において、Ｙアドレス方向に延在する複数のスペアラインの各々は、Ｘアドレス方向に移動し、メモリセル領域１００においてＹアドレス方向に存在する不良セル（例えば符号Ｃ１１のライン上の不良セル）を同時救済する能力がある。なお、スペアラインの移動とは、実際に物理的に移動するという意味ではなく、置換によって擬似的に移動しているように見えることを指す。このように、Ｘアドレス方向を移動範囲とし、Ｙアドレス方向に存在する不良セルの同時救済能力を有するスペアラインの集合を、スペアライングループＸＳＬＧと呼ぶ。また、図９において、Ｘアドレス方向に延在する複数のスペアラインの各々は、Ｙアドレス方向に移動し、メモリセル領域１００においてＸアドレス方向に存在する不良セル（例えば符号Ｒ１１のライン上の不良セル）を同時救済する能力がある。このように、Ｙアドレス方向を移動範囲とし、Ｘアドレス方向に存在する不良セルの同時救済能力を有するスペアラインの集合を、スペアライングループＹＳＬＧと呼ぶ。
【０００６】
メモリセル領域１００内における不良セルの分布（フェイル分布）が図９に示す通りであるとすると、符号Ｒ１１のライン上に配列されたメモリセルをスペアライングループＹＳＬＧの中の１本のスペアラインで置換すると共に、符号Ｃ１１、Ｃ１２、Ｃ１３のライン上に配列されたメモリセルをスペアライングループＸＳＬＧの中の３本のスペアラインで置換することにより、メモリデバイスの不良を救済することができる。なお、以下では、符号Ｃ１１、Ｃ１２、Ｃ１３、Ｒ１１のように、フェイルが存在するラインをフェイルラインと呼ぶ。
【０００７】
上記のように、メモリセル領域１００におけるフェイル分布（つまりフェイルライン）に対するスペアラインの最適な割当パターンを演算によって求めることをリダンダンシ演算という。従来のリダンダンシ演算では、フェイル数の多いフェイルラインから優先的にスペアラインを割当てる方法や、下記特許文献１に記載されているように、スペアライングループ毎にスペアラインの１本当たりのコストを求め、このスペアラインの１本当たりのコストから算出される救済効率を基にスペアラインの割当てを行う方法などが考案されている。
【０００８】
特許文献１の技術について具体的に説明すると、あるスペアライングループのリペア候補ラインの本数及び各リペア候補ライン上の未救済フェイル数を基に、そのスペアライングループの全体コストを算出し、当該全体コストをスペアライングループに属するスペアラインの本数で除算することにより、スペアラインの１本当たりのコストを算出する。ここで、リペア候補ラインとは、１本のスペアラインについて、フェイル上に割当て可能なライン（フェイルライン）の候補を指す（但し、同じスペアライングループに属するスペアラインは区別しない）。例えば、図９におけるスペアライングループＸＳＬＧに属するスペアラインのリペア候補ラインは、符号Ｃ１１、Ｃ１２、Ｃ１３、Ｃ１４、Ｃ１５のラインとなる。また、スペアライングループＹＳＬＧに属するスペアラインのリペア候補ラインは、符号Ｒ１１、Ｒ１２、Ｒ１３、Ｒ１４、Ｒ１５のラインとなる。
【０００９】
そして、１フェイル当たりの救済コストＣＲを、ＣＲ＝（スペアライン１本当たりのコスト）／（救済フェイル数）によって算出し、当該救済コストＣＲの逆数を救済効率（＝１／ＣＲ）とする。このようなコスト計算により、救済効率の高いリペア候補ラインを探索し、救済効率の高いリペア候補ラインに優先的にスペアラインの割当てを行い、全フェイル救済完了と判定されるまで、または救済不可能と判定されるまで、スペアラインの割当てを繰り返す。ここで、全フェイル救済完了と判定された場合、最終的に得られたスペアラインの割当パターンデータを用いて、実際のリダンダンシ処理（レーザトリマ）を行う。一方、全フェイルの救済は不可能と判定された場合、スペアラインの割当パターンを変更してリトライを行い、再度、全フェイル救済完了と判定されるまで、または救済不可能と判定されるまで、スペアラインの割当てを繰り返す。ここで、リトライ回数やリダンダンシ演算に要する時間が所定の閾値に到達した場合、最終的に救済不能デバイスと判断し、次のメモリデバイスのリダンダンシ演算を開始する。
【特許文献１】特開２００７−０６６３４９号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
ところで、近年においては、メモリデバイスの低価格化が進んでおり、試験に要するコストを含めたメモリデバイスの製造コストの低減が要求されている。このため、メモリ試験装置を用いた試験時間及びメモリデバイスの不良救済に要する時間（つまりリダンダンシ演算に要する時間）等を極力短縮する必要がある。上述したメモリデバイスの不良救済は製造歩留まりを向上させて製造コストを低減する上で必要不可欠なものであり、メモリデバイスの不良救済を行う場合には救済が可能であるメモリデバイスのみが全数救済されるというのが理想的である。
【００１１】
しかしながら、従来のリダンダンシ演算では、上述したように、救済効率の高いリペア候補ラインに優先的にスペアラインの割当てを行うため、最終的に全フェイル救済完了となるのか、または救済不可能となるのかはスペアラインの割当てが終了するまでわからなかった。このため、フェイル分布やデバイス構造（スペアラインの配置構造）によっては、リトライ回数が増大すると共にリダンダンシ演算に要する時間が増大し、本来ならば救済可能であったメモリデバイスを救済不能デバイスと判断して廃棄してしまうという問題があった。つまりメモリデバイスの救済率の低下を招いていた。
【００１２】
近年、メモリデバイスの大容量化に伴い、デバイス構造、つまりスペアラインの配置構造はますます複雑化しており、上述した従来のリダンダンシ演算では、このような複雑な構造を有するメモリデバイスに対応することは困難となっていた。
【００１３】
本発明は、このような事情に鑑みてなされたものであり、メモリデバイスの構造に依存しない汎用性を備えると共にリダンダンシ演算の高速化を図り、メモリデバイスの救済率の向上を図ることのできるリダンダンシ演算装置及びリダンダンシ演算方法並びにメモリ試験装置を提供することを目的とする。
【課題を解決するための手段】
【００１４】
上記課題を解決するために、本発明では、リダンダンシ演算装置に係る第１の解決手段として、複数のメモリセルが行アドレス方向及び列アドレス方向に２次元配列されたメモリセル領域の周辺に、複数の予備セルからなるスペアラインが設けられたメモリデバイスの不良救済を行う上で、前記メモリセル領域におけるフェイル分布に対する前記スペアラインの割当パターンを演算によって求めるリダンダンシ演算装置であって、全てのフェイルが救済されるための条件を第１の制約条件とし、同一の救済能力を有するスペアラインの集合であるスペアライングループ毎に使用されるスペアラインの本数を制限するための条件を第２の制約条件とし、フェイルの救済に使用されるスペアラインの総数、またはスペアラインをフェイルの救済に使用した場合に発生する総コストを目的関数とし、前記第１及び第２の制約条件の下、前記目的関数を最小化するという最適化問題を０−１整数計画法を適用して解くことにより、前記メモリセル領域におけるフェイル分布に対する前記スペアラインの割当パターンを求める演算処理部を備える、ことを特徴とする。
【００１５】
また、本発明では、リダンダンシ演算装置に係る第２の解決手段として、上記第１の解決手段において、前記演算処理部は、１本のスペアラインについて、前記メモリセル領域におけるフェイル上に割当可能なラインの候補をリペア候補ラインｊ（ｊ＝１、２、・・・、ｎ）とし、リペア候補ラインｊがフェイルｉ（ｉ＝１、２、・・・、Ｍ）を救済する場合を「１」、救済しない場合を「０」とする係数ｒｉｊと、リペア候補ラインｊがスペアライングループｋ（ｋ＝１、２、・・・、Ｋ）に属する場合を「１」、属さない場合を「０」とする係数ｇｋｊと、リペア候補ラインｊを採用する場合を「１」、採用しない場合を「０」とする変数ｘｊとを定義し、前記係数ｒｉｊと変数ｘｊとから成る下記（１５）式を、全てのフェイルが救済されるための第１の制約条件とし、前記係数ｇｋｊと変数ｘｊとから成る下記（１８）式を、スペアライングループｋ毎に使用されるスペアラインの本数を制限するための第２の制約条件とし、スペアライングループｋによって定まるコストｗｋと前記係数ｇｋｊと前記変数ｘｊとから成る下記（２０）式で表される総コストｚを目的関数とし、前記第１及び第２の制約条件の下、前記目的関数ｚを最小化するという最適化問題を０−１整数計画法を適用して解くことにより、ｘｊの最適解を求める、ことを特徴とする。
【００１６】
【数１】
【００１７】
また、本発明では、リダンダンシ演算装置に係る第３の解決手段として、上記第２の解決手段において、前記演算処理部は、下記（２１）式で表される行列Ａ、ｂ、ｘ、ｃを作成し、前記目的関数ｚを下記（２２）式で置き換え、前記第１及び第２の制約条件を下記（２３）式で置き換えることを特徴とする。
【００１８】
【数２】
【００１９】
また、本発明では、リダンダンシ演算装置に係る第４の解決手段として、上記第２または第３の解決手段において、前記メモリデバイスにおける前記スペアライングループの配置構造に応じた演算条件データを予め記憶する演算条件データ記憶部と、前記メモリセル領域におけるフェイルのアドレスを示すフェイルアドレスデータを記憶するフェイルアドレス記憶部と、を備え、前記演算処理部は、前記演算条件データ及び前記フェイルアドレスデータを基に、リペア候補ラインｊがフェイルｉを救済するか否かを判別することにより、前記係数ｒｉｊを作成することを特徴とする。
【００２０】
また、本発明では、リダンダンシ演算装置に係る第５の解決手段として、上記第４の解決手段において、前記演算条件データは、前記スペアライングループの救済領域であるメモリセル領域の原点位置を規定するベースアドレスデータと、スペアライングループの行アドレス方向及び列アドレス方向の幅を規定するマスクデータと、スペアライングループの救済可能範囲を規定するリペアマスクデータとで構成されることを特徴とする。
【００２１】
また、本発明では、リダンダンシ演算装置に係る第６の解決手段として、上記第５の解決手段において、前記演算処理部は、前記演算条件データの内、前記マスクデータと前記リペアマスクデータとの論理和をとった結果のビット反転データを判定用マスクデータとし、当該判定用マスクデータと前記フェイルアドレスデータとの論理和をとった結果が、前記ベースアドレスデータと一致した場合に、リペア候補ラインｊがフェイルｉを救済すると判別することを特徴とする。
【００２２】
また、本発明では、リダンダンシ演算装置に係る第７の解決手段として、上記第１〜第６のいずれかの解決手段において、前記０−１整数計画法の解法として、間接列挙法を適用した分枝限定法を用いることを特徴とする。
【００２３】
一方、本発明では、リダンダンシ演算方法に係る解決手段として、複数のメモリセルが行アドレス方向及び列アドレス方向に２次元配列されたメモリセル領域の周辺に、複数の予備セルからなるスペアラインが設けられたメモリデバイスの不良救済を行う上で、前記メモリセル領域におけるフェイル分布に対する前記スペアラインの割当パターンを演算によって求めるリダンダンシ演算方法であって、全てのフェイルが救済されるための条件を第１の制約条件とし、同一の救済能力を有するスペアラインの集合であるスペアライングループ毎に使用されるスペアラインの本数を制限するための条件を第２の制約条件とし、フェイルの救済に使用されるスペアラインの総数、またはスペアラインをフェイルの救済に使用した場合に発生する総コストを目的関数とし、前記第１及び第２の制約条件の下、前記目的関数を最小化するという最適化問題を０−１整数計画法を適用して解くことにより、前記メモリセル領域におけるフェイル分布に対する前記スペアラインの割当パターンを求める、ことを特徴とする。
【００２４】
さらに、本発明では、メモリ試験装置に係る解決手段として、メモリデバイスのパス／フェイルを示すフェイル情報を格納するフェイルメモリを有するメモリ試験装置であって、前記フェイルメモリに格納された前記フェイル情報を用いて、前記メモリデバイスのメモリセル領域におけるフェイル分布に対する前記スペアラインの割当パターンを演算によって求める請求項１〜請求項７のいずれか一項に記載のリダンダンシ演算装置を備えることを特徴とする。
【発明の効果】
【００２５】
本発明に係るリダンダンシ演算装置は、全てのフェイルが救済されるための条件を第１の制約条件とし、同一の救済能力を有するスペアラインの集合であるスペアライングループ毎に使用されるスペアラインの本数を制限するための条件を第２の制約条件とし、フェイルの救済に使用されるスペアラインの総数、またはスペアラインをフェイルの救済に使用した場合に発生する総コストを目的関数とし、前記第１及び第２の制約条件の下、前記目的関数を最小化するという最適化問題を０−１整数計画法を適用して解くことにより、メモリセル領域におけるフェイル分布に対するスペアラインの割当パターンを求めるものである。
【００２６】
すなわち、従来のリダンダンシ演算では、救済効率の高いリペア候補ラインに優先的にスペアラインの割当てを行うため、最終的に全フェイル救済完了となるのか、または救済不可能となるのかはスペアラインの割当てが終了するまでわからなかったが、本発明では、リダンダンシ演算の始めから全てのフェイルが救済されるための制約条件を考慮して、目的関数を最小化するという最適化問題を解くため、得られた最適解は必ず全フェイルの救済を満足していることになる。従って、本発明に係るリダンダンシ演算装置によれば、従来では必要であったリトライが不要となるので、メモリデバイスの構造に依存しない汎用性を備えることができると共に、リダンダンシ演算の高速化を図ることが可能であり、その結果、メモリデバイスの救済率の向上を図ることが可能である。
【発明を実施するための最良の形態】
【００２７】
以下、図面を参照して、本発明の一実施形態について説明する。
図１は、本発明の一実施形態におけるリダンダンシ演算装置を備えるメモリ試験装置の要部構成を示すブロック図である。図１に示す通り、メモリ試験装置１０は、試験パターン発生部１１、アドレス変換部１２、コンパレータ１３、フェイルメモリコントローラ１４、フェイルメモリ１５及びリダンダンシ演算装置２０を備えており、複数（例えば、数百個）のメモリデバイス３０の試験を並列して行う。なお、メモリデバイス３０は、Ｘアドレス（列アドレス）及びＹアドレス（行アドレス）により個々が特定される複数のメモリセルが２次元配列されたメモリセル領域と、メモリセル領域の周囲に、ライン状に形成された複数の予備セルからなるスペアラインを有する。なお、詳細は後述するが、メモリデバイス３０内のアドレスは、上記のＸアドレス及びＹアドレスの他、ページという要素も含めた３次元の要素によって定義されている。
【００２８】
試験パターン発生部１１は、メモリデバイス３０に与える試験パターンＤ１及び二次元のアドレスＡ１並びにパス／フェイル判定時に用いる期待値Ｄ３を発生する。アドレス変換部１２は、所定の変換規則に従って、試験パターン発生部１１で発生した二次元のアドレスＡ１を一次元のアドレスＡ２に変換する。コンパレータ１３は、メモリデバイス３０から読み出されたデータＤ２と試験パターン発生部１１から出力される期待値Ｄ３とを比較してパス／フェイルを示すフェイルデータＦＤを出力する。フェイルメモリコントローラ１４は、フェイルメモリ１５に対するフェイルデータＦＤの書き込み制御及び読み出し制御を行う。フェイルメモリ１５は、複数のメモリデバイス３０の試験結果を示すフェイルデータＦＤを記憶するものであり、その容量は例えば数百ギガビット程度である。
【００２９】
リダンダンシ演算装置２０は、フェイルが発生したメモリデバイス３０のメモリセル領域におけるフェイル分布（つまりフェイルライン）に対するスペアラインの最適な割当パターンを、０−１整数計画法を用いたリダンダンシ演算によって求めるものであり、演算処理部２１、演算条件データ記憶部２２、フェイルアドレス記憶部２３及び表示部２４を備えている。
【００３０】
演算処理部２１は、フェイルメモリコントローラ１４を介してフェイルメモリ１５からフェイルデータＦＤを取得すると共に、当該フェイルデータＦＤからフェイルが発生したメモリセルのアドレス（以下、フェイルアドレスと称す）を抽出し、このフェイルアドレスを所定のデータ表現形式のフェイルアドレスデータに変換してフェイルアドレス記憶部２３に記憶する。また、この演算処理部２１は、演算条件データ記憶部２２に記憶されている演算条件データと、フェイルアドレス記憶部２３に記憶されているフェイルアドレスデータとに基づいて、フェイルが発生したメモリデバイス３０のメモリセル領域におけるフェイルラインに対するスペアラインの最適な割当パターンを、０−１整数計画法を用いたリダンダンシ演算によって求める。なお、この演算処理部２１による０−１整数計画法を用いたリダンダンシ演算についての詳細は後述する。
【００３１】
演算条件データ記憶部２２は、ＤＵＴ３０に設けられたスペアラインの配置構造を規定する演算条件データを予め記憶しており、上記演算処理部２１の制御の下、演算条件データを演算処理部２１に出力する。フェイルアドレス記憶部２３は、上記演算処理部２１の制御の下、上記フェイルアドレスデータを記憶する一方、要求に応じてフェイルアドレスデータを演算処理部２１に出力する。表示部２４は、例えば液晶ディスプレイであり、演算処理部２１の制御の下、リダンダンシ演算の演算結果を表示する。
【００３２】
以下、上記の演算条件データ及びフェイルアドレスデータについて詳細に説明する。図２は、メモリデバイス３０におけるメモリセル領域及びスペアラインの配置構造を示す概念図である。図２に示すように、メモリセル領域はブロック単位（ＢＬＫ１、ＢＬＫ２、ＢＬＫ３）に区分されており、それぞれのブロックは独立して動作し、互いに影響を及ぼさない。本実施形態におけるリダンダンシ演算装置２０（演算処理部２１）は、このブロック毎にリダンダンシ演算を行う。
【００３３】
また、図２に示すように、１つのブロック内には、予備セル領域であるスペアラインが形成されており、以下では、同一の救済能力を有するスペアラインの集合をスペアライングループ（ＸＳＬＧ１、ＸＳＬＧ２、ＹＳＬＧ）と呼ぶ。本実施形態では、これらスペアライングループの救済メモリセル領域を、セグメント（ＳＥＧ１、ＳＥＧ２）という領域で定義する。つまり、図２の例では、スペアライングループＸＳＬＧ１に属するスペアラインは、Ｘアドレス方向を移動範囲とし、セグメントＳＥＧ１のＹアドレス方向に存在する不良セル（以下、フェイルと略す）の同時救済能力を有する。また、スペアライングループＸＳＬＧ２に属するスペアラインは、Ｘアドレス方向を移動範囲とし、セグメントＳＥＧ２のＹアドレス方向に存在するフェイルの同時救済能力を有する。また、スペアライングループＹＳＬＧに属するスペアラインは、Ｙアドレス方向を移動範囲とし、セグメントＳＥＧ１及びＳＥＧ２のＸアドレス方向に存在するフェイルの同時救済能力を有する。
【００３４】
本実施形態では、上記のような構造のメモリデバイス３０内の位置を指定するためのアドレスを、Ｘアドレス及びＹアドレスに、ページＰを加えた３次元要素（Ｐ、Ｘ、Ｙ）によって定義する。メモリデバイス３０がページ構造を有しないデバイスである場合、ページＰ＝０とすれば良い。このような３次元要素からなるアドレスを用いることによって、セグメントやスペアライングループ、フェイルの位置などを定義することができる。
【００３５】
本実施形態では、スペアライングループを、ベースアドレスデータ、マスクデータ、リペアマスクデータの３つのデータによって定義する。ベースアドレスデータとは、スペアライングループの救済領域であるセグメントの原点位置を規定するデータである。マスクデータとは、スペアライングループによって同時救済可能な領域、つまりスペアライングループのＸアドレス方向及びＹアドレス方向の幅を規定するデータである。リペアマスクデータとは、スペアライングループの移動可能範囲（救済可能範囲）を規定するデータである。本実施形態では、これら３つのデータを１組の演算条件データとする。この演算条件データは、スペアライングループの配置構造によって変わるため、メモリデバイス３０におけるスペアライングループの配置構造に応じて演算条件データを作成し、演算条件データ記憶部２２に予め記憶しておく。
【００３６】
図３及び図４は、所定のスペアライングループの配置構造に対応する演算条件データの一例を示したものである。図３（ａ）は、Ｘアドレス方向を移動範囲とし、セグメントＳＥＧ１のＹアドレス方向に存在するフェイルの同時救済能力を有するスペアライングループＸＳＬＧ１の演算条件データである。ここで、Ｘアドレス「０」〜「ＦＦ」（１６進数）、Ｙアドレス「０」〜「ＦＦ」で定義される領域をセグメントＳＥＧ１とする。つまり、セグメントＳＥＧ１はＸアドレス方向及びＹアドレス方向に「１００（＝２５６＝２８）」の幅を有している。
【００３７】
演算条件データ（ベースアドレスデータ、マスクデータ、リペアマスクデータ）は、ページＰに対応するページビット領域ＰＢと、Ｙアドレスに対応するＹアドレスビット領域ＹＢと、Ｘアドレスに対応するＸアドレスビット領域ＸＢとで構成されている。ページビット領域ＰＢのビット数はメモリデバイス３０が有するページ数に応じて設定すれば良いが、Ｙアドレスビット領域ＹＢ及びＸアドレスビット領域ＸＢでは、少なくとも１つのセグメントに対応可能なビット数（つまり８ビット）が必要である。なお、図３及び図４において、ページビット領域ＰＢ、Ｙアドレスビット領域ＹＢ、Ｘアドレスビット領域ＸＢの斜線部分はビットが「１」にセットされていることを示し、白抜き部分はビットが「０」にセットされていることを示している。
【００３８】
図３（ａ）に示すように、セグメントＳＥＧ１を救済するスペアライングループＸＳＬＧ１のベースアドレスデータは救済領域（セグメントＳＥＧ１）の原点を規定するデータであるので、Ｙアドレスビット領域ＹＢ及びＸアドレスビット領域ＸＢの全ビットは「０」（１６進数で「０」）にセットされる。また、マスクデータはスペアライングループＸＳＬＧ１によって同時救済可能な領域を規定するデータなので、Ｙアドレスビット領域ＹＢの８ビット分は「１」（１６進数で「ＦＦ」）にセットされ、Ｘアドレスビット領域ＸＢの全ビットは「０」にセットされる。つまり、このマスクデータによって、スペアライングループＸＳＬＧ１は、セグメントＳＥＧ１内のＹアドレス方向に対して１ライン上に存在するフェイルを同時救済可能であることを定義している。また、リペアマスクデータはスペアライングループＸＳＬＧ１の移動可能範囲を規定するデータなので、Ｘアドレスビット領域ＸＢの８ビット分は「１」（１６進数で「ＦＦ」）にセットされ、Ｙアドレスビット領域ＹＢの全ビットは「０」にセットされる。つまり、このリペアマスクデータによって、スペアライングループＸＳＬＧ１は、セグメントＳＥＧ１内のＸアドレス方向に移動可能であることを定義している。
【００３９】
図３（ｂ）は、Ｙアドレス方向を移動範囲とし、セグメントＳＥＧ１のＸアドレス方向に存在するフェイルの同時救済能力を有するスペアライングループＹＳＬＧ１の演算条件データである。この図に示すように、スペアライングループＹＳＬＧ１のベースアドレスデータにおいて、Ｙアドレスビット領域ＹＢ及びＸアドレスビット領域ＸＢの全ビットは「０」（１６進数で「０」）にセットされる。また、マスクデータにおいて、Ｘアドレスビット領域ＸＢの８ビット分は「１」（１６進数で「ＦＦ」）にセットされ、Ｙアドレスビット領域ＹＢの全ビットは「０」にセットされる。また、リペアマスクデータにおいて、Ｙアドレスビット領域ＹＢの８ビット分は「１」（１６進数で「ＦＦ」）にセットされ、Ｘアドレスビット領域ＸＢの全ビットは「０」にセットされる。
【００４０】
図４（ａ）は、Ｙアドレス方向を移動範囲とし、セグメントＳＥＧ１及びＳＥＧ２のＸアドレス方向に存在するフェイルの同時救済能力を有するスペアライングループＹＳＬＧ１−２の演算条件データである。なお、Ｘアドレス「１００」〜「１ＦＦ」（１６進数）、Ｙアドレス「０」〜「ＦＦ」で定義される領域をセグメントＳＥＧ２とする。この図に示すように、スペアライングループＹＳＬＧ１-２のベースアドレスデータにおいて、Ｙアドレスビット領域ＹＢ及びＸアドレスビット領域ＸＢの全ビットは「０」（１６進数で「０」）にセットされる。また、マスクデータにおいて、Ｘアドレスビット領域ＸＢの９ビット分は「１」（１６進数で「１ＦＦ」）にセットされ、Ｙアドレスビット領域ＹＢの全ビットは「０」にセットされる。また、リペアマスクデータにおいて、Ｙアドレスビット領域ＹＢの８ビット分は「１」（１６進数で「ＦＦ」）にセットされ、Ｘアドレスビット領域ＸＢの全ビットは「０」にセットされる。
【００４１】
図４（ｂ）は、Ｘアドレス方向を移動してセグメントＳＥＧ１を救済すると共に、連動してセグメントＳＥＧ２を同時救済する能力を有するスペアライングループＸＳＬＧ１＆２の演算条件データである。この図に示すように、スペアライングループＸＳＬＧ１＆２のベースアドレスデータにおいて、Ｙアドレスビット領域ＹＢ及びＸアドレスビット領域ＸＢの全ビットは「０」（１６進数で「０」）にセットされる。また、マスクデータにおいて、Ｘアドレスビット領域ＸＢの９ビット目は「１」（１６進数で「１００」）にセットされ、Ｙアドレスビット領域ＹＢの全ビットは「１」（１６進数で「ＦＦ」）にセットされる。また、リペアマスクデータにおいて、Ｘアドレスビット領域ＸＢの８ビット分は「１」（１６進数で「ＦＦ」）にセットされ、Ｙアドレスビット領域ＹＢの全ビットは「０」にセットされる。
【００４２】
このスペアライングループＸＳＬＧ１＆２の演算条件データは、以下のような作成方法を用いる。マスクデータを作成する場合、まず、図５に示すように、スペアライングループがセグメントＳＥＧ１を救済する場合のベースアドレスデータ（Ｙアドレスビット領域ＹＢ及びＸアドレスビット領域ＸＢの全ビット「０」）と、スペアライングループがセグメントＳＥＧ２を救済する場合のベースアドレスデータ（Ｘアドレスビット領域ＸＢの９ビット目「１」、Ｙアドレスビット領域ＹＢの全ビット「０」）との排他的論理和をとる。そして、その排他的論理和の結果と、スペアライングループがセグメントＳＥＧ１を救済する場合のマスクデータ（Ｙアドレスビット領域ＹＢの８ビット分は「１」、Ｘアドレスビット領域ＸＢの全ビット「０」）との論理和をとり、これにより得られたデータをスペアライングループＸＳＬＧ１＆２のマスクデータとして使用する。また、ベースアドレスデータ及びリペアマスクデータとしては、セグメントＳＥＧ１を救済する場合のベースアドレスデータ及びリペアマスクデータを使用する。
なお、図４（ａ）のようなスペアライングループＹＳＬＧ１-２の演算条件データを作成する場合も同様の手法を用いることができる。
【００４３】
図４（ｃ）は、Ｘアドレス方向を移動してセグメントＳＥＧ１またはＳＥＧ２の一方を救済する能力を有するスペアライングループＸＳＬＧ１｜２の演算条件データである。この図に示すように、スペアライングループＸＳＬＧ１｜２のベースアドレスデータにおいて、Ｙアドレスビット領域ＹＢ及びＸアドレスビット領域ＸＢの全ビットは「０」（１６進数で「０」）にセットされる。また、マスクデータにおいて、Ｙアドレスビット領域ＹＢの８ビット分は「１」（１６進数で「ＦＦ」）にセットされ、Ｘアドレスビット領域ＸＢの全ビットは「０」にセットされる。また、リペアマスクデータにおいて、Ｘアドレスビット領域ＸＢの９ビット分は「１」（１６進数で「１ＦＦ」）にセットされ、Ｙアドレスビット領域ＹＢの全ビットは「０」にセットされる。
【００４４】
このスペアライングループＸＳＬＧ１｜２の演算条件データは、以下のような作成方法を用いる。リペアマスクデータを作成する場合、まず、スペアライングループがセグメントＳＥＧ１を救済する場合のベースアドレスデータと、スペアライングループがセグメントＳＥＧ２を救済する場合のベースアドレスデータとの排他的論理和をとる。そして、その排他的論理和の結果と、スペアライングループがセグメントＳＥＧ１を救済する場合のリペアマスクデータとの論理和をとり、これにより得られたデータをスペアライングループＸＳＬＧ１｜２のリペアマスクデータとして使用する。また、ベースアドレスデータ及びマスクデータとしては、セグメントＳＥＧ１を救済する場合のベースアドレスデータ及びマスクデータを使用する。
【００４５】
以上説明したような救済能力を有するスペアライングループがメモリデバイス３０内のメモリセル領域（セグメント）に応じて複数設けられており、各スペアライングループに応じた演算条件データが演算条件データ記憶部２２に予め記憶されている。
なお、フェイルアドレス記憶部２２に記憶されるフェイルアドレスデータも演算条件データと同様に、ページビット領域ＰＢ、Ｙアドレスビット領域ＹＢ、Ｘアドレスビット領域ＸＢから構成されている。つまり、演算処理部２１は、フェイルメモリコントローラ１４を介してフェイルメモリ１５からフェイルデータＦＤを取得すると共に、当該フェイルデータＦＤからフェイルアドレスを抽出し、このフェイルアドレスを上記のように、ページビット領域ＰＢ、Ｙアドレスビット領域ＹＢ、Ｘアドレスビット領域ＸＢから構成されるフェイルアドレスデータに変換してフェイルアドレス記憶部２３に記憶する。
【００４６】
次に、上記のように構成されたメモリ試験装置１０の動作について説明する。
メモリ試験装置１０は、まずメモリデバイス３０の試験を行い、次いで、フェイルが発生したメモリデバイス３０のメモリセル領域（セグメント）におけるフェイル分布に対するスペアラインの最適な割当パターンを、０−１整数計画法を用いたリダンダンシ演算によって求める。
【００４７】
メモリデバイス３０の試験が開始されると、まず試験パターン発生部１１から試験パターンＤ１とアドレスＡ１とが出力されて、試験パターンＤ１がメモリデバイス３０に書き込まれる。試験パターンＤ１の書き込みが終了すると、試験パターン発生部１１からアドレスＡ１と期待値Ｄ３とが出力される。
【００４８】
試験パターン発生部１１から出力されたアドレスＡ１がメモリデバイス３０に与えられると、メモリデバイス３０に予め書き込んだ試験パターンがデータＤ２として読み出されてコンパレータ１３に入力され、試験パターン発生部１１から出力された期待値Ｄ３と比較されてパス／フェイルが判定され、パス／フェイルを示すフェイルデータＦＤがフェイルメモリコントローラ１４に入力される。また、試験パターン発生部１１から出力されたアドレスＡ１は、アドレス変換部１２に出力されて一次元のアドレスＡ２に変換されフェイルメモリコントローラ１４に入力される。フェイルメモリコントローラ１４は、アドレスＡ２で示されるフェイルメモリ１５の記憶領域に、コンパレータ１３から出力されたフェイルデータＦＤを書き込む。試験パターン発生部１１からアドレスＡ１及び期待値Ｄ３が出力される度に上記の動作が繰り返し行われ、これによりフェイルデータＦＤがフェイルメモリ１５に順次記憶される。
【００４９】
メモリデバイス３０の試験が終了すると、リダンダンシ演算装置２０の演算処理部２１は、フェイルメモリコントローラ１４を制御してフェイルメモリ１５に記憶されたフェイルデータＦＤを読み出すと共に、フェイルデータＦＤからフェイルアドレスを抽出し、このフェイルアドレスをページビット領域ＰＢ、Ｙアドレスビット領域ＹＢ、Ｘアドレスビット領域ＸＢから構成されるフェイルアドレスデータに変換してフェイルアドレス記憶部２３に記憶する。演算処理部２１は、フェイルアドレス記憶部２３へのフェイルアドレスデータの記憶処理が完了すると、以下に説明するリダンダンシ演算を行う。
【００５０】
まず、本実施形態における０−１整数計画法を用いたリダンダンシ演算の原理について説明する。
【００５１】
＜０−１整数計画法＞
０−１整数計画法とは、変数ｘｊ及び係数ｃｊから成る（１）式で表される一次関数を目的関数ｚとし、変数ｘｊ、係数ａｉｊ及び係数ｂｊから成る（２）式で表される一次不等式の制約条件と、変数ｘｊが「０」または「１」の値しか取らないという（３）式で表される制約条件の下で、上記目的関数ｚを最小化または最大化するという最適化問題を解くことをいう。
【００５２】
【数３】
【００５３】
上記（１）、（２）、（３）式で表される０−１整数計画法の解の個数は２ｎ個である。よって、それらを全て列挙して逐一実行可能であるか否かを確認し、実行可能であれば、その目的関数ｚを求めることによってこの最適化問題を解くことができることは明らかである。しかしながら、変数ｘｊの個数ｎの値が大きくなると解の個数は指数関数的に増大するため、上記のように解の全てを列挙する方法を用いると演算時間が膨大となる恐れがある。そこで、このような０−１整数計画法の解法として、間接列挙法を適用した分枝限定法を用いる。この間接列挙法は変数の０−１条件を積極的に利用した解法である。
【００５４】
＜分枝限定法、間接列挙法＞
直接的な解法が見つかっていない最適化問題Ｐ０が与えられている場合、（４）式に示すように、適当な条件を設定して、Ｐ０の実行可能領域Ｘ０をいくつかの部分領域Ｘ１、Ｘ２、・・・Ｘｋに分割し、その各々に対応する問題Ｐｋを考え、これをＰ０の子問題という。この一群の子問題Ｐｋ（ｋ＝１、２、・・・）を解いて得られた解の中でｆ（ｘ）の値が最小のものを見つければ、問題Ｐ０の最適解が得られることは明らかである。この子問題Ｐ０がまだ直接解けない場合は、Ｘｋをさらにいくつかの領域に分け、Ｐｋをさらにいくつかの子問題に分解する。このような手順を繰り返すことで、元の問題Ｐ０を解く方法が分枝限定法である。
【００５５】
【数４】
【００５６】
この分枝限定法は、分枝操作と限定操作とで構成されている。分枝操作とは、問題Ｐｋが直接解けない場合、その実行可能領域となるＸｋを（５）式で表されるいくつかの部分集合Ｘｐ、・・・、Ｘｑに分割し、Ｐｋをその一群の子問題である（６）式で置き換えることである。
【００５７】
【数５】
【００５８】
一般に、Ｐｋの実行可能領域Ｘｋは、Ｘ０に制限を加えたＸｋ＝Ｘ０∩Ｂｋという形で与えられている。ここで、（７）式で表されるＢｋ，ｐ、・・・、Ｂｋ，ｑを用いて、Ｘｌを（８）式とすることにより、（５）式を満たす分割が得られる。
【００５９】
【数６】
【００６０】
上記のような子問題への分枝操作を終端させる操作を限定操作という。この限定操作では、（４）式の制約条件をさらに緩めた緩和問題Ｐｋ’を解くことになる。
【００６１】
【数７】
【００６２】
ここで、問題Ｐｋと緩和問題Ｐｋ’の間には次の関係が成立する。
(i)Ｐｋ’が実行可能解を持たない時は、Ｐｋも実行可能解を持たない。
(ii)Ｐｋ’の最適解をｘ’としたとき、ｘ’∈Ｘｋならばｘ’はＰｋの最適解である。
(iii)Ｐｋ’の最適値をｚ’とし、Ｐｋの最適値をｚ＊とすると、ｚ’＜ｚ＊である。
【００６３】
問題Ｐ０の少なくとも１つの実行可能解ｘ”が得られているとし、ｘ”に対応する目的関数値をｚ”＝ｆ’（ｘ”）とすると、ｚ”はＰ０の暫定的な最適値となる。従って、Ｐｋ’の最適値ｚｋ’が下記（１０）式を満たせば、問題Ｐｋのいかなる実行可能解もｘ”より良い目的関数値を与えないことが明らかである。よって、この場合、Ｐｋをこれ以上分枝することは無意味であり、このような場合、Ｐｋは限定操作によって見切られて分枝停止となる。さらに、Ｐｋ’の最適解ｘｋ’が下記（１１）式を満たす場合、ｘｋ’はＰｋの最適解となる。よって、この場合もＰｋを分枝する必要はない。
【００６４】
【数８】
【００６５】
このように（１０）式または（１１）式が成立するか否かを調べることを子問題Ｐｋを探査するといい、（１０）式または（１１）式が成立したことが判明した場合、子問題Ｐｋは探査済みとなり、それ以上分枝しても無意味なので、この時点で子問題Ｐｋは分枝停止となる。分枝限定法とは、上記のような分枝操作と限定操作を繰り返すことによって、元の問題Ｐ０を解くものである。
【００６６】
また、上記（８）式において、Ｂｋ，ｌとして、下記（１２）式を用いることにより、列挙する解の個数を減らすことができる。このように、０−１条件を利用して列挙する解の個数を減らし、効率良く問題を解く方法が間接列挙法である。
【００６７】
【数９】
【００６８】
＜０−１整数計画法を用いたリダンダンシ演算＞
次に、上記のような０−１整数計画法の原理を応用した、本実施形態におけるリダンダンシ演算について説明する。
まず、リペア候補ライン（１本のスペアラインについて、フェイル上に割当て可能なライン（フェイルライン）の候補）を数え上げて、通し番号ｊ＝１、２、・・・、ｎで表す（但し、同じスペアライングループに属するスペアラインは区別しない）。また、フェイルを通し番号ｉ＝１、２、・・・、Ｍで表し、スペアライングループを通し番号ｋ＝１、２、・・・、Ｋで表す。なお、計算量を減らすために、フェイルを救済しないスペアライングループは除外しておく。
【００６９】
ここで、係数ｒｉｊと変数ｘｊを、下記（１３）及び（１４）式のように定義すると、全てのフェイルが救済されるための条件は、下記（１５）式で表される。また、どのリペア候補ラインも少なくとも１つはフェイルを救済するため、付帯条件として下記（１６）式が成立する。
【００７０】
【数１０】
【００７１】
また、スペアライングループｋに属するスペアラインの本数をＬｋとし、係数ｇｋｊを下記（１７）式のように定義すると、スペアライングループｋ毎に使用されるスペアラインの本数を制限するための条件は、下記（１８）式で表すことができる。また、どのリペア候補ラインも属するスペアライングループの数は１つであるから、付帯条件として下記（１９）式が成立する。
【００７２】
【数１１】
【００７３】
ここで、スペアラインを使用すると、属するスペアライングループｋによって定まるコストｗｋが発生する場合がある。この時の総コストｚは、下記（２０）で表すことができる。
【００７４】
【数１２】
【００７５】
全てのフェイルを救済して、総コストｚを最小化するという最適化問題を考えると、以下に示すように、（１５）式を第１の制約条件、（１８）式を第２の制約条件とし、上記（２０）式を目的関数とした、０−１整数計画問題として定式化される。
【００７６】
【数１３】
【００７７】
ここで、下記（２１）式に示すような、行列Ａ、ｂ、ｘ、ｃを定義すると、目的関数及び制約条件は、下記（２２）、（２３）式のように表すことができる。
【００７８】
【数１４】
【００７９】
このように、本実施形態におけるリダンダンシ演算では、上記（２３）式で表される制約条件の下、（２２）式で表される目的関数ｚを最小化するという最適化問題を解き、ｘｊの最適解を求めることにより、あるブロックのフェイル分布に対して、全フェイルを救済し且つ総コストｚを最小化することのできるスペアラインの割当パターンを求める。そして、リダンダンシ演算における０−１整数計画法の解法として、上述した間接列挙法を適用した分枝限定法を用いる。
【００８０】
具体的には、リダンダンシ演算における最適化問題の規模の縮小化については以下のように行う。あるフェイルｉ’に対して、リペア候補ラインがｊ’の１通りしかない場合、リペア候補ラインｊ’の採用が確定し、ｘｊ’＝１と定まる。この時、行列Ａの第ｊ’列と、行列ｘ、ｃの第ｊ’行は削除することができ、行列ｂは、ｂ−（Ａの第ｊ’列）、すなわち、下記（２４）式で置き換えることができる。
【００８１】
【数１５】
【００８２】
この結果、行列ｂｎｅｗの第ｉ’行の成分は、１−ｒｉ’ｊ’なので零となるが、その他にも第ｉ行（１＜ｉ＜Ｍ）が零ならば、フェイルｉも同時に救済されているので、このような行は全て行列Ａ、ｂｎｅｗから削除することができる。また、行列ｂｎｅｗの第Ｍ＋ｋ行（１＜ｋ＜Ｋ）が零ならば、スペアライングループｋのスペアラインは全て使い果たしているので、このような行を行列Ａ、ｂｎｅｗから削除する。スペアライングループｋに属するリペア候補ラインｊ（すなわち、ｇｋｊ＝１となるｊ）についてはｘｊ＝０と定まるので、行列Ａの第ｊ列と、行列ｘ、ｃの第ｊ行も削除することができる。このような操作を繰り返した結果、行列Ａの第ｉ行（１＜ｉ＜Ｍ）の成分が全て零となった場合、フェイルｉは救済不可能と判定される。
【００８３】
この他、最適化問題の規模を縮小する方法として、救済できるフェイル数が大きなリペア候補ラインｊの採用を確定する（ｘｊ＝１）という方法も考えられる。また、その他のヒューリスティックな方法によって採用するリペア候補ラインを確定していくと、同様に問題規模を縮小することができる。
【００８４】
以下、リダンダンシ演算装置２０の演算処理部２１によって実行されるリダンダンシ演算の処理手順について、図６のフローチャートを参照して説明する。
【００８５】
まず、演算処理部２１は、演算条件データ記憶部２２から演算条件データを読み込むと共に、フェイルアドレスデータ記憶部２３からフェイルアドレスデータを読み込む（ステップＳ１）。そして、演算処理部２１は、演算条件データの内、マスクデータとリペアマスクデータを用いて判定用マスクデータを作成する（ステップＳ２）。
【００８６】
ここで、判定用マスクデータとは、マスクデータとリペアマスクデータとの論理和をとり、その結果得られたデータにビット反転を施して得られるデータである。図７に、図３（ａ）のスペアライングループＸＳＬＧ１に対応する演算条件データから作成した判定用マスクデータを示す。この判定用マスクデータは、上記（１３）式で表される係数ｒｉｊを作成するため、つまり、あるリペア候補ラインｊが、あるフェイルｉを救済可能か否かを判別するために用いられるデータであり、判定用マスクデータとフェイルアドレスデータとの論理和をとることで得られたアドレスデータが、そのリペア候補ラインｊが属するスペアライングループのベースアドレスデータと一致する場合、そのリペア候補ラインｊはフェイルｉを救済可能であると判別することができる。
【００８７】
このように、演算処理部２１は、判定用マスクデータとフェイルアドレスデータとの論理和をとることで得られたアドレスデータが、そのリペア候補ラインｊが属するスペアライングループのベースアドレスデータと一致するか否かを判別することによって、そのリペア候補ラインｊはフェイルｉを救済可能であるか否かを判別して係数ｒｉｊを作成する他、上記（１７）式で表される係数ｇｉｊを作成して、（２１）式で表される各行列を作成する（ステップＳ３）。そして、演算処理部２１は、上述したような０−１整数計画法の解法として、間接列挙法を適用した分枝限定法を用いて、（２２）（２３）式で表される最適化問題を解き、ｘｊの最適解（以下、救済解と称す）を求めることにより、あるブロックのフェイル分布に対して、全フェイルを救済し且つ総コストｚを最小化することのできるスペアラインの割当パターンを求める（ステップＳ４）。
【００８８】
そして、演算処理部２１は、上記ステップＳ４における演算結果を表示部２４に表示させる（ステップＳ５）。具体的には、演算処理部２１は、救済解を求めることができればスペアラインの割当パターンを表示部２４に表示させ、救済解を求めることができなければ「救済不可能」というメッセージを表示部２４に表示させる。そして、演算処理部２１は、救済解を求めることができた場合、実際のリダンダンシ処理を行う（レーザトリマ等によってスペアラインとフェイルラインとの置換を行う）レーザリペア装置に、使用するスペアラインのアドレス（リペアアドレス）を通知する（ステップＳ６）。なお、このレーザリペア装置が、メモリ試験装置１０内に設けられていない場合、一旦、演算結果を所定の記憶部に記憶しておき、全てのメモリデバイス３０の試験とリダンダンシ演算が終了した後、上記記憶部に記憶されている演算結果を記憶媒体に格納して、レーザリペア装置に演算結果を移動させるようにしても良い。
【００８９】
本願発明者は、様々なフェイル分布やスペアライングループの配置構造を用いて、上述した本実施形態におけるリダンダンシ演算の検証を行い、例えば図８に示すような基本的なスペアライングループの配置構造では、フェイル数が多くてもリダンダンシ演算に要する時間は数ｍｓｅｃ程度であるという結果を得ることができ、また、救済不可能な条件でリダンダンシ演算を行った場合は、正確に救済不可能という演算結果を得ることができた。図８は、リダンダンシ演算の検証に用いたフェイル分布及びスペアライングループの配置構造の一例である。図８（ａ）は、スペアライングループＸＳＬＧ１及びＹＳＬＧ１の配置構造を示し、図８（ｂ）は、セグメントＳＥＧ１におけるフェイル分布（フェイルアドレス）を示し、図８（ｃ）は、本実施形態におけるリダンダンシ演算の結果として得られたスペアラインの割当パターンを示している。
さらに、従来のリダンダンシ演算では救済解を得ることができなかったフェイル分布及びスペアライングループの配置構造を用いて、本実施形態におけるリダンダンシ演算の検証を行った結果、数十ｍｓｅｃ程度の短時間で救済解を得ることができた。
【００９０】
以上説明したように、本実施形態におけるリダンダンシ演算装置２０では、全てのフェイルが救済されるための条件を第１の制約条件とし、同一の救済能力を有するスペアラインの集合であるスペアライングループ毎に使用されるスペアラインの本数を制限するための条件を第２の制約条件とし、スペアラインをフェイルの救済に使用した場合に発生する総コストを目的関数とし、上記第１及び第２の制約条件の下、上記目的関数（総コスト）を最小化するという最適化問題を０−１整数計画法を適用して解くことにより、メモリセル領域（セグメント）におけるフェイル分布に対するスペアラインの割当パターンを求める。
【００９１】
すなわち、従来のリダンダンシ演算では、救済効率の高いリペア候補ラインに優先的にスペアラインの割当てを行うため、最終的に全フェイル救済完了となるのか、または救済不可能となるのかはスペアラインの割当てが終了するまでわからなかったが、本実施形態におけるリダンダンシ演算では、演算の始めから（１５）式で表される全てのフェイルが救済されるための制約条件を考慮して、目的関数を最小化するという最適化問題を解くため、得られた救済解は必ず全フェイルの救済を満足していることになる。従って、本実施形態のリダンダンシ演算によれば、従来では必要であったリトライが不要となるので、メモリデバイスの構造に依存しない汎用性を備えることができると共に、リダンダンシ演算の高速化を図ることが可能であり、その結果、メモリデバイス３０の救済率の向上を図ることが可能である。
【００９２】
また、本実施形態のリダンダンシ演算では０−１整数計画法を用いるため、変数ｘｊは「１」または「０」の値しか取り得ず、リダンダンシ演算の高速化に寄与する。さらに、０−１整数計画法の解法として、間接列挙法を適用した分枝限定法を用いることにより、さらにリダンダンシ演算の高速化を図ることが可能である
【００９３】
なお、上記実施形態において、スペアラインをフェイルの救済に使用した場合に発生する総コストｚを目的関数としたが、これに限らず、フェイルの救済に使用されるスペアラインの総数を目的関数とし、この使用されるスペアラインの総数を最小化するという最適化問題を０−１整数計画法を適用して解くようにしても良い。この場合、（２０）式において、係数ｃｊを削除すれば良い。
【００９４】
また、上記実施形態では、メモリ試験装置１０内にリダンダンシ演算装置２０が設けられている場合を想定して説明したが、これに限らず、リダンダンシ演算装置２０を別個に設け、メモリ試験装置１０からフェイル情報を取得するような構成としても良い。
【図面の簡単な説明】
【００９５】
【図１】本発明の一実施形態に係るリダンダンシ演算装置２０を備えたメモリ試験装置１０の構成ブロック図である。
【図２】本発明の一実施形態に係るメモリデバイス３０の内部構造を示す概念図である。
【図３】本発明の一実施形態に係るリダンダンシ演算装置２０における演算条件データ記憶部２２に記憶されている演算条件データの第１の例である。
【図４】本発明の一実施形態に係るリダンダンシ演算装置２０における演算条件データ記憶部２２に記憶されている演算条件データの第２の例である。
【図５】演算条件データにおけるマスクデータの作成方法を示す説明図である。
【図６】本発明の一実施形態に係るリダンダンシ演算装置２０における演算処理部２１が実行するリダンダンシ演算のフローチャートである。
【図７】リダンダンシ演算で使用される判定用マスクデータの作成方法を示す説明図である。
【図８】本発明の一実施形態に係るリダンダンシ演算装置２０にて行われるリダンダンシ演算の検証例である。
【図９】リダンダンシ処理の説明図である。
【符号の説明】
【００９６】
１０…メモリ試験装置、１１…試験パターン発生部、１２…アドレス変換部、１３…コンパレータ、１４…フェイルメモリコントローラ、１５…フェイルメモリ、２０…リダンダンシ演算装置、２１…演算処理部、２２…演算条件データ記憶部、２３…フェイルアドレス記憶部、２４…表示部、３０…メモリデバイス
【特許請求の範囲】
【請求項１】
複数のメモリセルが行アドレス方向及び列アドレス方向に２次元配列されたメモリセル領域の周辺に、複数の予備セルからなるスペアラインが設けられたメモリデバイスの不良救済を行う上で、前記メモリセル領域におけるフェイル分布に対する前記スペアラインの割当パターンを演算によって求めるリダンダンシ演算装置であって、
全てのフェイルが救済されるための条件を第１の制約条件とし、
同一の救済能力を有するスペアラインの集合であるスペアライングループ毎に使用されるスペアラインの本数を制限するための条件を第２の制約条件とし、
フェイルの救済に使用されるスペアラインの総数、またはスペアラインをフェイルの救済に使用した場合に発生する総コストを目的関数とし、
前記第１及び第２の制約条件の下、前記目的関数を最小化するという最適化問題を０−１整数計画法を適用して解くことにより、前記メモリセル領域におけるフェイル分布に対する前記スペアラインの割当パターンを求める演算処理部を備える、
ことを特徴とするリダンダンシ演算装置。
【請求項２】
前記演算処理部は、
１本のスペアラインについて、前記メモリセル領域におけるフェイル上に割当可能なラインの候補をリペア候補ラインｊ（ｊ＝１、２、・・・、ｎ）とし、
リペア候補ラインｊがフェイルｉ（ｉ＝１、２、・・・、Ｍ）を救済する場合を「１」、救済しない場合を「０」とする係数ｒｉｊと、
リペア候補ラインｊがスペアライングループｋ（ｋ＝１、２、・・・、Ｋ）に属する場合を「１」、属さない場合を「０」とする係数ｇｋｊと、
リペア候補ラインｊを採用する場合を「１」、採用しない場合を「０」とする変数ｘｊとを定義し、
前記係数ｒｉｊと変数ｘｊとから成る下記（１５）式を、全てのフェイルが救済されるための第１の制約条件とし、
前記係数ｇｋｊと変数ｘｊとから成る下記（１８）式を、スペアライングループｋ毎に使用されるスペアラインの本数を制限するための第２の制約条件とし、
スペアライングループｋによって定まるコストｗｋと前記係数ｇｋｊと前記変数ｘｊとから成る下記（２０）式で表される総コストｚを目的関数とし、
前記第１及び第２の制約条件の下、前記目的関数ｚを最小化するという最適化問題を０−１整数計画法を適用して解くことにより、ｘｊの最適解を求める、
ことを特徴とする請求項１記載のリダンダンシ演算装置。
【数１】
【請求項３】
前記演算処理部は、
下記（２１）式で表される行列Ａ、ｂ、ｘ、ｃを作成し、前記目的関数ｚを下記（２２）式で置き換え、前記第１及び第２の制約条件を下記（２３）式で置き換えることを特徴とする請求項２記載のリダンダンシ演算装置。
【数２】
【請求項４】
前記メモリデバイスにおける前記スペアライングループの配置構造に応じた演算条件データを予め記憶する演算条件データ記憶部と、
前記メモリセル領域におけるフェイルのアドレスを示すフェイルアドレスデータを記憶するフェイルアドレス記憶部と、を備え、
前記演算処理部は、前記演算条件データ及び前記フェイルアドレスデータを基に、リペア候補ラインｊがフェイルｉを救済するか否かを判別することにより、前記係数ｒｉｊを作成することを特徴とする請求項２または３記載のリダンダンシ演算装置。
【請求項５】
前記演算条件データは、前記スペアライングループの救済領域であるメモリセル領域の原点位置を規定するベースアドレスデータと、スペアライングループの行アドレス方向及び列アドレス方向の幅を規定するマスクデータと、スペアライングループの救済可能範囲を規定するリペアマスクデータとで構成されることを特徴とする請求項４記載のリダンダンシ演算装置。
【請求項６】
前記演算処理部は、前記演算条件データの内、前記マスクデータと前記リペアマスクデータとの論理和をとった結果のビット反転データを判定用マスクデータとし、当該判定用マスクデータと前記フェイルアドレスデータとの論理和をとった結果が、前記ベースアドレスデータと一致した場合に、リペア候補ラインｊがフェイルｉを救済すると判別することを特徴とする請求項５記載のリダンダンシ演算装置。
【請求項７】
前記０−１整数計画法の解法として、間接列挙法を適用した分枝限定法を用いることを特徴とする請求項１〜６のいずれか一項に記載のリダンダンシ演算装置。
【請求項８】
複数のメモリセルが行アドレス方向及び列アドレス方向に２次元配列されたメモリセル領域の周辺に、複数の予備セルからなるスペアラインが設けられたメモリデバイスの不良救済を行う上で、前記メモリセル領域におけるフェイル分布に対する前記スペアラインの割当パターンを演算によって求めるリダンダンシ演算方法であって、
全てのフェイルが救済されるための条件を第１の制約条件とし、
同一の救済能力を有するスペアラインの集合であるスペアライングループ毎に使用されるスペアラインの本数を制限するための条件を第２の制約条件とし、
フェイルの救済に使用されるスペアラインの総数、またはスペアラインをフェイルの救済に使用した場合に発生する総コストを目的関数とし、
前記第１及び第２の制約条件の下、前記目的関数を最小化するという最適化問題を０−１整数計画法を適用して解くことにより、前記メモリセル領域におけるフェイル分布に対する前記スペアラインの割当パターンを求める、
ことを特徴とするリダンダンシ演算方法。
【請求項９】
メモリデバイスのパス／フェイルを示すフェイル情報を格納するフェイルメモリを有するメモリ試験装置であって、
前記フェイルメモリに格納された前記フェイル情報を用いて、前記メモリデバイスのメモリセル領域におけるフェイル分布に対する前記スペアラインの割当パターンを演算によって求める請求項１〜請求項７のいずれか一項に記載のリダンダンシ演算装置を備えることを特徴とするメモリ試験装置。
【請求項１】
複数のメモリセルが行アドレス方向及び列アドレス方向に２次元配列されたメモリセル領域の周辺に、複数の予備セルからなるスペアラインが設けられたメモリデバイスの不良救済を行う上で、前記メモリセル領域におけるフェイル分布に対する前記スペアラインの割当パターンを演算によって求めるリダンダンシ演算装置であって、
全てのフェイルが救済されるための条件を第１の制約条件とし、
同一の救済能力を有するスペアラインの集合であるスペアライングループ毎に使用されるスペアラインの本数を制限するための条件を第２の制約条件とし、
フェイルの救済に使用されるスペアラインの総数、またはスペアラインをフェイルの救済に使用した場合に発生する総コストを目的関数とし、
前記第１及び第２の制約条件の下、前記目的関数を最小化するという最適化問題を０−１整数計画法を適用して解くことにより、前記メモリセル領域におけるフェイル分布に対する前記スペアラインの割当パターンを求める演算処理部を備える、
ことを特徴とするリダンダンシ演算装置。
【請求項２】
前記演算処理部は、
１本のスペアラインについて、前記メモリセル領域におけるフェイル上に割当可能なラインの候補をリペア候補ラインｊ（ｊ＝１、２、・・・、ｎ）とし、
リペア候補ラインｊがフェイルｉ（ｉ＝１、２、・・・、Ｍ）を救済する場合を「１」、救済しない場合を「０」とする係数ｒｉｊと、
リペア候補ラインｊがスペアライングループｋ（ｋ＝１、２、・・・、Ｋ）に属する場合を「１」、属さない場合を「０」とする係数ｇｋｊと、
リペア候補ラインｊを採用する場合を「１」、採用しない場合を「０」とする変数ｘｊとを定義し、
前記係数ｒｉｊと変数ｘｊとから成る下記（１５）式を、全てのフェイルが救済されるための第１の制約条件とし、
前記係数ｇｋｊと変数ｘｊとから成る下記（１８）式を、スペアライングループｋ毎に使用されるスペアラインの本数を制限するための第２の制約条件とし、
スペアライングループｋによって定まるコストｗｋと前記係数ｇｋｊと前記変数ｘｊとから成る下記（２０）式で表される総コストｚを目的関数とし、
前記第１及び第２の制約条件の下、前記目的関数ｚを最小化するという最適化問題を０−１整数計画法を適用して解くことにより、ｘｊの最適解を求める、
ことを特徴とする請求項１記載のリダンダンシ演算装置。
【数１】
【請求項３】
前記演算処理部は、
下記（２１）式で表される行列Ａ、ｂ、ｘ、ｃを作成し、前記目的関数ｚを下記（２２）式で置き換え、前記第１及び第２の制約条件を下記（２３）式で置き換えることを特徴とする請求項２記載のリダンダンシ演算装置。
【数２】
【請求項４】
前記メモリデバイスにおける前記スペアライングループの配置構造に応じた演算条件データを予め記憶する演算条件データ記憶部と、
前記メモリセル領域におけるフェイルのアドレスを示すフェイルアドレスデータを記憶するフェイルアドレス記憶部と、を備え、
前記演算処理部は、前記演算条件データ及び前記フェイルアドレスデータを基に、リペア候補ラインｊがフェイルｉを救済するか否かを判別することにより、前記係数ｒｉｊを作成することを特徴とする請求項２または３記載のリダンダンシ演算装置。
【請求項５】
前記演算条件データは、前記スペアライングループの救済領域であるメモリセル領域の原点位置を規定するベースアドレスデータと、スペアライングループの行アドレス方向及び列アドレス方向の幅を規定するマスクデータと、スペアライングループの救済可能範囲を規定するリペアマスクデータとで構成されることを特徴とする請求項４記載のリダンダンシ演算装置。
【請求項６】
前記演算処理部は、前記演算条件データの内、前記マスクデータと前記リペアマスクデータとの論理和をとった結果のビット反転データを判定用マスクデータとし、当該判定用マスクデータと前記フェイルアドレスデータとの論理和をとった結果が、前記ベースアドレスデータと一致した場合に、リペア候補ラインｊがフェイルｉを救済すると判別することを特徴とする請求項５記載のリダンダンシ演算装置。
【請求項７】
前記０−１整数計画法の解法として、間接列挙法を適用した分枝限定法を用いることを特徴とする請求項１〜６のいずれか一項に記載のリダンダンシ演算装置。
【請求項８】
複数のメモリセルが行アドレス方向及び列アドレス方向に２次元配列されたメモリセル領域の周辺に、複数の予備セルからなるスペアラインが設けられたメモリデバイスの不良救済を行う上で、前記メモリセル領域におけるフェイル分布に対する前記スペアラインの割当パターンを演算によって求めるリダンダンシ演算方法であって、
全てのフェイルが救済されるための条件を第１の制約条件とし、
同一の救済能力を有するスペアラインの集合であるスペアライングループ毎に使用されるスペアラインの本数を制限するための条件を第２の制約条件とし、
フェイルの救済に使用されるスペアラインの総数、またはスペアラインをフェイルの救済に使用した場合に発生する総コストを目的関数とし、
前記第１及び第２の制約条件の下、前記目的関数を最小化するという最適化問題を０−１整数計画法を適用して解くことにより、前記メモリセル領域におけるフェイル分布に対する前記スペアラインの割当パターンを求める、
ことを特徴とするリダンダンシ演算方法。
【請求項９】
メモリデバイスのパス／フェイルを示すフェイル情報を格納するフェイルメモリを有するメモリ試験装置であって、
前記フェイルメモリに格納された前記フェイル情報を用いて、前記メモリデバイスのメモリセル領域におけるフェイル分布に対する前記スペアラインの割当パターンを演算によって求める請求項１〜請求項７のいずれか一項に記載のリダンダンシ演算装置を備えることを特徴とするメモリ試験装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２００９−６４５１５（Ｐ２００９−６４５１５Ａ）
【公開日】平成２１年３月２６日（２００９．３．２６）
【国際特許分類】
【出願番号】特願２００７−２３１５６９（Ｐ２００７−２３１５６９）
【出願日】平成１９年９月６日（２００７．９．６）
【出願人】（５０４１４５３６４）国立大学法人群馬大学 (352)
【出願人】（０００００６５０７）横河電機株式会社 (4,443)
【Ｆターム（参考）】
【公開日】平成２１年３月２６日（２００９．３．２６）
【国際特許分類】
【出願日】平成１９年９月６日（２００７．９．６）
【出願人】（５０４１４５３６４）国立大学法人群馬大学 (352)
【出願人】（０００００６５０７）横河電機株式会社 (4,443)
【Ｆターム（参考）】
[ Back to top ]