(57)【特許請求の範囲】
【請求項１】
半導体デバイスのメモリーブロックならびに予備ラインおよびリンボの不良ビットの位置を示す情報をもとに、予備ラインによりメモリーブロックの不良ビットを救済するために、現実のメモリーブロックならびに予備ラインおよびリンボからなる救済対象に対して仮想的な予備ラインにより、該メモリーブロックならびに予備ラインおよびリンボのビット不良を救済する第１の解を求め、この求められた第１の解に基づいて、現実の予備ラインによりメモリーブロックの不良ビットを救済する第２の解を求める半導体不良ビット救済処理方法であって、
前記第１の解のうち、前記仮想的な予備ラインにより救済された現実のメモリーブロックのラインを、現実の予備ラインで救済するラインとして決定するとともに、前記第１の解のうち、仮想的な予備ラインにより救済された現実の予備ライン以外の現実の予備ラインを、救済に使用可能な予備ラインとして決定し、この決定にもとづいて救済するメモリーブロックのラインとその救済に使用する予備ラインとの対応関係を決定することを特徴とする半導体不良ビット救済処理方法。
【請求項２】
前記第１の解を求めるに際し、現実のメモリーブロックと現実の予備ラインとの間に保持される対応関係に対応するように現実のメモリーブロックならびに予備ラインおよびリンボからなる救済対象に対して仮想的な予備ラインを与え、現実のメモリーブロックを救済するにあたって現実の予備ラインに与えられている制約条件に対応する条件を仮想的な予備ラインに与えて、前記第１の解を求めることを特徴とする請求項１記載の半導体不良ビット救済処理方法。
【請求項３】
前記第１の解を求めるに際し、現実のメモリーブロックと現実の予備ラインとの間に保持される対応関係に対応するように現実のメモリーブロックならびに予備ラインおよびリンボからなる救済対象に対して仮想的な予備ラインを与え、現実のメモリーブロックを救済するにあたって現実の予備ラインに与えられている制約条件のうち所定の条件を仮想的な予備ラインに与えて、前記第１の解の候補を求め、この求められた候補が前記制約条件の残りの条件を満たす場合に、この候補を求めるべき前記第１の解とすることを特徴とする請求項１記載の半導体不良ビット救済処理方法。
【請求項４】
前記第１の解を求めるに際し、現実のメモリーブロックならびに予備ラインおよびリンボに含まれる全ての不良ビットについて行識別子と列識別子の２つの座標要素で特定される位置情報を表現する２部グラフを作成し、作成された２部グラフからＤＭ分解およびその縮約グラフを算出し、算出されたＤＭ分解およびその縮約グラフにもとづいて、仮想的な予備ラインとこれにより救済されるメモリーブロックにおける不良ビットを含むラインとの対応関係を求めることを特徴とする請求項１記載の半導体不良ビット救済処理方法。
【請求項５】
前記第１の解を求めるに際し、現実のメモリーブロックならびに予備ラインおよびリンボに含まれる全ての不良ビットについて行識別子と列識別子の２つの座標要素で特定される位置情報を表現する２部グラフを作成し、作成された２部グラフからＤＭ分解およびその縮約グラフを算出し、算出されたＤＭ分解およびその縮約グラフにもとづいて前記第１の解を求める第１の処理を実行し、現実のメモリーブロックならびに予備ラインおよびリンボに含まれる全ての不良ビットの位置情報、予備ラインの使用方法に関する制約条件および予備ラインの本数制限、現実のメモリーブロックを救済する仮想の予備ラインの最小化を整数計画問題で表現し、その整数解として前記第１の解を求める第２の処理を、前記第１の処理の実行結果をバックアップするために、実行することを特徴とする請求項１記載の半導体不良ビット救済処理方法。
【請求項６】
規定された時間だけ前記第１の処理を実行しても前記第１の解が得られなかった場合に、前記第２の処理を実行することを特徴とする請求項５記載の半導体不良ビット救済処理方法。
【請求項７】
前記第１の解を求めるに際し、現実のメモリーブロックならびに予備ラインおよびリンボに含まれる全ての不良ビットの位置情報、予備ラインの使用方法に関する制約条件および予備ラインの本数制限、現実のメモリーブロックを救済する仮想の予備ラインの最小化を整数計画問題で表現し、その整数解として前記第１の解を求めることを特徴とする請求項１記載の半導体不良ビット救済処理方法。
【請求項８】
前記整数計画問題を、整数条件を実数条件に緩和して線形計画問題として解き、整数解が得られた場合に、これを求めるべき前記第１の解とすることを特徴とする請求項５または７記載の半導体不良ビット救済処理方法。
【請求項９】
前記第１の解を求める手順には、全ての不良ビットを救済できる解が存在しないことを検出する手順を含むことを特徴とする請求項１記載の半導体不良ビット救済処理方法。
【請求項１０】
前記第１の解を求めるに際し、仮想的な予備ラインの使用の態様を変えた複数の解を求め、求められた解のうち、使用すべき現実の予備ラインの数を最小とするものを求めるべき前記第１の解とすることを特徴とする請求項１記載の半導体不良ビット救済処理方法。
【請求項１１】
前記第１の解を求めるに際し、前処理としてラインフェイルを救済する解を求め、前処理において救済された不良ビットを除いた全不良ビットを、前処理において使用した仮想的な予備ラインを除いた残りの仮想的な予備ラインにより救済する解を求め、これら解を結合したものを求めるべき前記１の解とすることを特徴とする請求項１記載の半導体不良ビット救済処理方法。
【請求項１２】
救済対象となる半導体デバイスのメモリーブロックならびに予備ラインおよびリンボから構成される処理単位が、垂直方向の予備ラインは前記メモリーブロックの垂直方向の長さを持つ１本のラインとして垂直方向の所与のブロックに属す不良ラインに割当て可能であり且つ水平方向の予備ラインは前記メモリーブロックの水平方向の長さを持つ１本のラインとして水平方向の所与のブロックに属す不良ラインに割当て可能である、という条件を満たさない場合に、予備ラインによりメモリーブロックの不良ビットを救済する半導体不良ビット救済処理方法において、前記条件を満たすように前記処理単位を分割して形成した複数の部分処理単位夫々ごとに、予備ラインによりメモリーブロックの不良ビットを救済する解の候補を求め、前記部分処理単位夫々の解の候補を合成して前記処理単位の解を生成することを特徴とする半導体不良ビット救済処理方法。
【請求項１３】
前記部分処理単位夫々は少なくとも１つの他の部分処理単位との間で一部の予備ライン群を共用するものであり、前記部分処理単位夫々の解の候補を合成するに際しては、複数の部分処理単位間でのスペア群の共用形態を考慮して、前記処理単位の解を生成することを特徴とする請求項１２に記載の半導体不良ビット救済処理方法。
【請求項１４】
前記部分処理単位の解の候補を合成するに際して、複数の前記部分処理単位間で共用されている予備ライン群については、当該予備ライン群を共用する部分処理単位の解の候補のうちの少なくとも１つにおいて当該予備ライン群のうちで使用不可とされたものの和集合を、当該予備ライン群における使用不可の予備ラインの集合として、当該予備ライン群に関する前記処理単位の解を求めることを特徴とする請求項１３に記載の半導体不良ビット救済処理方法。
【請求項１５】
前記部分処理単位の解の候補を合成するに際して、使用不可の予備ライン以外の予備ラインを用いたメモリブロックの不良ビットの救済処理を、各部分処理単位について逐次的に行うとともに、当該部分処理単位の解の候補において使用不可となっている予備ラインおよびそれまでの救済処理において使用済みとなった予備ラインの和集合を当該部分処理単位における使用不可の予備ラインとして、前記処理単位の解を求めることを特徴とする請求項１２または１３に記載の半導体不良ビット救済処理方法。
【請求項１６】
救済対象となる半導体デバイスのメモリーブロックならびに予備ラインおよびリンボから構成される処理単位が、垂直方向の予備ラインは前記メモリーブロックの垂直方向の長さを持つ１本のラインとして垂直方向の所与のブロックに属す不良ラインに割当て可能であり且つ水平方向の予備ラインは前記メモリーブロックの水平方向の長さを持つ１本のラインとして水平方向の所与のブロックに属す不良ラインに割当て可能であるという条件を満たさない場合に、予備ラインによりメモリーブロックの不良ビットを救済する半導体不良ビット救済処理装置において、前記条件を満たすように前記処理単位を分割して形成した複数の部分処理単位夫々ごとに、予備ラインによりメモリーブロックの不良ビットを救済する解の候補を求める手段と、前記部分処理単位夫々の解の候補を合成して前記処理単位の解を生成する手段とを備えたことを特徴とする半導体不良ビット救済処理装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、メモリセルの不良をスペアで救済するための解を求める半導体不良ビット救済処理方法及び半導体不良ビット救済処理装置に関する。
【０００２】
【従来の技術】
従来、Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｉｅｓ（ＲＡＭｓ）と呼ばれる半導体メモリーの集積度がまだそれ程高くないときは、製造初期にある程度のビット不良が発生しても、これを製造条件の改善等で解消してきた。
【０００３】
しかし、半導体メモリーの容量の増大にともなって、ビット不良の解消を図ろうとするだけでなく、ある程度のビット不良の発生を前提として、ビット不良を救済する（ビット不良を含むラインを代替する）スペアと呼ばれる予備ラインを設ける技術が開発された。スペアを設ければ、実質的な集積度は減るが、結局、生産性などの観点で有利だからである。
【０００４】
このスペアの技術を利用する場合、まず、メモリーテスタ装置（あるいはビット・フェイル・テスタ装置等）において不良ビットを検出した後、不良ビットの位置に応じて、所定本数ずつ設けられた行スペアと列スペアのうちどのスペアでどの不良ラインを救済するかについて決定する処理を、スペアの使用方法に制約がある場合にはそれを考慮しつつ行い、この結果に従ってリペア装置においてチップ上に設けられた切替アドレス設定用のヒューズをレーザで切断するなどして各スペアで代替すべきラインのアドレスを設定する。
【０００５】
以下、上記処理の従来技術における問題点に関して詳しく説明する。上記のように半導体メモリーは、主要なメモリーアレー部分に加えて、スペアと呼ばれる予備ライン（行用のラインと列用のライン）を備えている。この予備ラインは、通常、修理を担当するメモリーアレー領域ごとに分けてまとめられて配置されている。不良ビットセルが検出されると、その不良ビットセルを含むライン（行ライン、列ライン）を不良ラインとして、そのラインを、その領域の修理を担当している予備ラインと交換する。全ての不良ビットセルが予備ラインで救済されるまで、不良ラインと予備ラインの交換を続ける。予備ラインにより全ての不良ビットセルが救済されれば、その半導体メモリーの救済は成功である。一方、全ての予備ラインが使われても、不良ビットセルが存在する場合（あるいはある担当範囲内での全予備ラインが使われても、その担当範囲内に不良ビットセルが存在する場合）は、救済不可と判定する。なお、上記救済処理にあたっては、救済可能な場合に使用する予備ライン数は最小であることが望ましい等、製造コストに関して最適な救済方法に関する判断基準が設けられている場合が多い。
【０００６】
従来の救済処理方法では、不良ラインと予備ラインとの間の対応付けに関して全ての組合せを計算して評価すると多大な計算時間を要することから、例えば、最も不良の多いラインから順に予備ラインを割り当てて行き、全ての予備ラインが割り当てられても救済できない場合は、溯って割り当てを変更する方法が取られていた。あるいは、左側の不良列（または上側の不良行）から順に予備ラインを割り当てて行き、全ての予備ラインが割り当てられても救済できない場合は、溯って割り当てを変更する方法が取られていた。
【０００７】
しかし、これら従来の救済方法では、救済可能な不良ラインと予備ラインの間の対応関係が存在する場合でも、限られた計算時間内では全ての組合せを確かめられないために、救済できる組合せを確かめるまでに制限時間になり救済不可と判定したり、あるいは救済できたとしても最適解には遠い救済解を提示（出力）することがあった。
【０００８】
特に、予備ラインに不良ビットセルが存在する場合はその予備ラインの適用の組合せも加わり、また、予備ラインが複数のメモリーアレイ領域を担当できる場合は複数の領域が一つの予備ラインを取り合うので、このような場合は組合せ数はさらに増大し、解を求めるのが困難になるという問題点があった。
【０００９】
近年、半導体メモリーは、その集積度とアーキテクチャの複雑性が益々高まり、従来の救済方法では、非常に簡単な不良の場合を除くとスペアによるライン交換の任意の組合せは莫大な数となり、その計算には時間がかかるために、限られた処理時間内では救済不可となる場合がさらに多くなって、生産性の低下となっている。
【００１０】
【発明が解決しようとする課題】
上述したように従来は、不良ラインを予備ラインで救済する解が存在する場合でも、救済不可とされることが多々発生するという問題があった。特に、予備ラインに不良ビットセルが存在する場合は、救済解の探索が一段と難しくなるという問題があった。
【００１１】
本発明は、上記事情を考慮してなされたものであり、予備ラインにより全不良ビットが救済可能か否かを短時間に判定することができ、また救済可能の場合には予備ラインの使用の仕方に関して最適もしくは準最適な解を提示することのできる半導体不良ビット救済処理方法及び半導体不良ビット救済処理装置を提供することを目的とする。
【００１２】
【課題を解決するための手段】
（１）本発明は、半導体デバイスにおけるビットデータを記憶するための第１のセルの不良ビットを予備として設けられた第２のセルにより救済する半導体不良ビット救済処理方法において、現実の第１のセルおよび第２のセルからなる救済対象に対して仮想的に与えた第３のセルにより、該現実の第１のセルおよび第２のセルの不良ビットを救済する手順を有することを特徴とする。
【００１３】
ここで、「救済する」とは、第１のセルに生じた不良ビットを、代替可能な第２のセルにより代替できるようにする程度の意味として用いている。
【００１４】
（２）本発明は、半導体デバイスのメモリーブロックの不良ビットを、予備として設けられた予備ラインにより救済する半導体不良ビット救済処理方法において、現実のメモリーブロックならびに予備ラインおよびリンボからなる救済対象に対して仮想的に与えた予備ラインにより、該メモリーブロックならびに予備ラインおよびリンボのビット不良を救済する手順を有することを特徴とする。
【００１５】
（３）本発明は、半導体デバイスのメモリーブロックならびに予備ラインおよびリンボの不良ビットの位置を示す情報をもとに、予備ラインによりメモリーブロックの不良ビットを救済する半導体不良ビット救済処理方法において、現実のメモリーブロックならびに予備ラインおよびリンボからなる救済対象に対して仮想的に与えた予備ラインにより、該メモリーブロックならびに予備ラインおよびリンボのビット不良を救済する解を求め、この求められた解に基づいて、現実の予備ラインによりメモリーブロックの不良ビットを救済する解を求めることを特徴とする。
【００１６】
（４）好ましくは、前記仮想的な予備ラインに係る解のうち、該仮想的な予備ラインにより救済された現実のメモリーブロックのラインを、現実の予備ラインで救済するラインとし、該仮想的な予備ラインに係る解のうち、仮想的な予備ラインにより救済された現実の予備ライン以外の現実の予備ラインを、救済に使用可能な予備ラインとするようにしてもよい。
【００１７】
（５）好ましくは、前記仮想的な予備ラインに係る解のうち、該仮想的な予備ラインにより救済された現実のメモリーブロックのラインを、現実の予備ラインで救済するラインとして決定するとともに、該仮想的な予備ラインに係る解のうち、仮想的な予備ラインにより救済された現実の予備ライン以外の現実の予備ラインを、救済に使用可能な予備ラインとして決定し、この決定にもとづいて救済するメモリーブロックのラインとその救済に使用する予備ラインとの対応関係を決定するようにしてもよい。
【００１８】
（６）好ましくは、仮想的な予備ラインにより現実のメモリーブロックならびに予備ラインおよびリンボからなる救済対象を救済する解を求めるに際し、現実のメモリーブロックと現実の予備ラインとの間に保持される対応関係に対応するように現実のメモリーブロックならびに予備ラインおよびリンボからなる救済対象に対して仮想的な予備ラインを与え、現実のメモリーブロックを救済するにあたって現実の予備ラインに与えられている制約条件に対応する条件を仮想的な予備ラインに与えて、前記解を求めるようにしてもよい。
【００１９】
（７）好ましくは、仮想的な予備ラインにより現実のメモリーブロックならびに予備ラインおよびリンボからなる救済対象を救済する解を求めるに際し、現実のメモリーブロックと現実の予備ラインとの間に保持される対応関係に対応するように現実のメモリーブロックならびに予備ラインおよびリンボからなる救済対象に対して仮想的な予備ラインを与え、現実のメモリーブロックを救済するにあたって現実の予備ラインに与えられている制約条件のうち所定の条件を仮想的な予備ラインに与えて、前記解を求め、この求められた解が前記制約条件の残りの条件を満たす場合に、この解を求めるべき解とするようにしてもよい。
【００２０】
（８）好ましくは、仮想的な予備ラインにより現実のメモリーブロックならびに予備ラインおよびリンボからなる救済対象を救済する解を求めるに際し、現実のメモリーブロックならびに予備ラインおよびリンボに含まれる全ての不良ビットについて行識別子と列識別子の２つの座標要素で特定される位置情報を表現する２部グラフを作成し、作成された２部グラフからＤＭ分解およびその縮約グラフを算出し、算出されたＤＭ分解およびその縮約グラフにもとづいて、仮想的な予備ラインとこれにより救済されるメモリーブロックにおける不良ビットを含むラインとの対応関係を求めるようにしてもよい。
【００２１】
（９）好ましくは、仮想的な予備ラインにより現実のメモリーブロックならびに予備ラインおよびリンボからなる救済対象を救済する解を求めるに際し、現実のメモリーブロックならびに予備ラインおよびリンボに含まれる全ての不良ビットについて行識別子と列識別子の２つの座標要素で特定される位置情報を表現する２部グラフを作成し、作成された２部グラフからＤＭ分解およびその縮約グラフを算出し、算出されたＤＭ分解およびその縮約グラフにもとづいて前記解を求める第１の処理を実行し、現実のメモリーブロックならびに予備ラインおよびリンボに含まれる全ての不良ビットの位置情報、予備ラインの使用方法に関する制約条件および予備ラインの本数制限、現実のメモリーブロックを救済する仮想の予備ラインの最小化を整数計画問題で表現し、その整数解として前記解を求める第２の処理を、前記第１の処理の実行結果をバックアップするために、実行するようにしてもよい。
【００２２】
（１０）好ましくは、規定された時間だけ前記第１の処理を実行しても解が得られなかった場合に、前記第２の処理を実行するようにしてもよい。
【００２３】
（１１）好ましくは、仮想的な予備ラインにより現実のメモリーブロックならびに予備ラインおよびリンボからなる救済対象を救済する解を求めるに際し、現実のメモリーブロックならびに予備ラインおよびリンボに含まれる全ての不良ビットの位置情報、予備ラインの使用方法に関する制約条件および予備ラインの本数制限、現実のメモリーブロックを救済する仮想の予備ラインの最小化を整数計画問題で表現し、その整数解として前記解を求めるようにしてもよい。
【００２４】
（１２）好ましくは、前記整数計画問題を、整数条件を実数条件に緩和して線形計画問題として解き、整数解が得られた場合に、これを求めるべき解とするようにしてもよい。
【００２５】
（１３）好ましくは、仮想的な予備ラインにより現実のメモリーブロックならびに予備ラインおよびリンボからなる救済対象を救済する解を求める手順には、全ての不良ビットを救済できる解が存在しないことを検出する手順を含むようにしてもよい。
【００２６】
（１４）好ましくは、仮想的な予備ラインにより現実のメモリーブロックならびに予備ラインおよびリンボからなる救済対象を救済する解を求めるに際し、仮想的な予備ラインの使用の態様を変えた複数の解を求め、求められた解のうち、使用すべき現実の予備ラインの数を最小とするものを求めるべき解とするようにしてもよい。
【００２７】
（１５）好ましくは、仮想的な予備ラインにより現実のメモリーブロックならびに予備ラインおよびリンボからなる救済対象を救済する解を求めるに際し、前処理としてラインフェイルを救済する解を求め、前処理において救済された不良ビットを除いた全不良ビットを、前処理において使用した仮想的な予備ラインを除いた残りの仮想的な予備ラインにより救済する解を求め、これら解を結合したものを求めるべき解とするようにしてもよい。
【００２８】
（１６）また、本発明は、半導体デバイスにおけるビットデータを記憶するための第１のセルの不良ビットを予備として設けられた第２のセルにより救済する解を求める半導体不良ビット救済処理装置において、現実の第１のセルおよび第２のセルからなる救済対象に対して仮想的に与えた第３のセルにより、該現実の第１のセルおよび第２のセルの不良ビットを救済する手段を備えたことを特徴とする。
【００２９】
また、本発明は、半導体デバイスのメモリーブロックの不良ビットを、予備として設けられた予備ラインにより救済する解を求める半導体不良ビット救済処理装置において、現実のメモリーブロックならびに予備ラインおよびリンボからなる救済対象に対して仮想的に与えた予備ラインにより、該メモリーブロックならびに予備ラインおよびリンボのビット不良を救済する処理手段を備えたことを特徴とする。
【００３０】
また、本発明は、半導体デバイスのメモリーブロックならびに予備ラインおよびリンボの不良ビットの位置を示す情報をもとに、予備ラインによりメモリーブロックの不良ビットを救済する解を求める半導体不良ビット救済処理装置において、現実のメモリーブロックならびに予備ラインおよびリンボからなる救済対象に対して仮想的に与えた予備ラインにより、該メモリーブロックならびに予備ラインおよびリンボのビット不良を救済する解を求める処理手段と、この手段により求められた前記解に基づいて、現実の予備ラインによりメモリーブロックの不良ビットを救済する解を求める手段とを備えたことを特徴とする。
【００３１】
好ましくは、現実の予備ラインによりメモリーブロックの不良ビットを救済する解を求める手段は、前記仮想的な予備ラインに係る解のうち、該仮想的な予備ラインにより救済された現実のメモリーブロックのラインを、現実の予備ラインで救済するラインとし、該仮想的な予備ラインに係る解のうち、仮想的な予備ラインにより救済された現実の予備ライン以外の現実の予備ラインを、救済に使用可能な予備ラインとするようにしてもよい。
【００３２】
好ましくは、現実の予備ラインによりメモリーブロックの不良ビットを救済する解を求める手段は、前記仮想的な予備ラインに係る解のうち、該仮想的な予備ラインにより救済された現実のメモリーブロックのラインを、現実の予備ラインで救済するラインとして決定するとともに、該仮想的な予備ラインに係る解のうち、仮想的な予備ラインにより救済された現実の予備ライン以外の現実の予備ラインを、救済に使用可能な予備ラインとして決定し、この決定にもとづいて救済するメモリーブロックのラインとその救済に使用する予備ラインとの対応関係を決定するようにしてもよい。
【００３３】
好ましくは、前記処理手段は、現実のメモリーブロックと現実の予備ラインとの間に保持される対応関係に対応するように現実のメモリーブロックならびに予備ラインおよびリンボからなる救済対象に対して仮想的な予備ラインを与え、現実のメモリーブロックを救済するにあたって現実の予備ラインに与えられている制約条件に対応する条件を仮想的な予備ラインに与えて、前記解を求めるようにしてもよい。
【００３４】
好ましくは、前記処理手段は、現実のメモリーブロックと現実の予備ラインとの間に保持される対応関係に対応するように現実のメモリーブロックならびに予備ラインおよびリンボからなる救済対象に対して仮想的な予備ラインを与え、現実のメモリーブロックを救済するにあたって現実の予備ラインに与えられている制約条件のうち所定の条件を仮想的な予備ラインに与えて、前記解を求め、この求められた解が前記制約条件の残りの条件を満たす場合に、この解を求めるべき解とするようにしてもよい。
【００３５】
好ましくは、前記処理手段は、現実のメモリーブロックならびに予備ラインおよびリンボに含まれる全ての不良ビットについて行識別子と列識別子の２つの座標要素で特定される位置情報を表現する２部グラフを作成し、作成された２部グラフからＤＭ分解およびその縮約グラフを算出し、算出されたＤＭ分解およびその縮約グラフにもとづいて、仮想的な予備ラインとこれにより救済されるメモリーブロックにおける不良ビットを含むラインとの対応関係を求めるようにしてもよい。
【００３６】
好ましくは、前記処理手段は、現実のメモリーブロックならびに予備ラインおよびリンボに含まれる全ての不良ビットについて行識別子と列識別子の２つの座標要素で特定される位置情報を表現する２部グラフを作成し、作成された２部グラフからＤＭ分解およびその縮約グラフを算出し、算出されたＤＭ分解およびその縮約グラフにもとづいて前記解を求める第１の処理を実行し、現実のメモリーブロックならびに予備ラインおよびリンボに含まれる全ての不良ビットの位置情報、予備ラインの使用方法に関する制約条件および予備ラインの本数制限、現実のメモリーブロックを救済する仮想の予備ラインの最小化を整数計画問題で表現し、その整数解として前記解を求める第２の処理を、前記第１の処理の実行結果をバックアップするために、実行するようにしてもよい。
【００３７】
好ましくは、前記処理手段は、規定された時間だけ前記第１の処理を実行しても解が得られなかった場合に、前記第２の処理を実行するようにしてもよい。
【００３８】
好ましくは、前記処理手段は、仮想的な予備ラインにより現実のメモリーブロックならびに予備ラインおよびリンボからなる救済対象を救済する解を求めるに際し、現実のメモリーブロックならびに予備ラインおよびリンボに含まれる全ての不良ビットの位置情報、予備ラインの使用方法に関する制約条件および予備ラインの本数制限、現実のメモリーブロックを救済する仮想の予備ラインの最小化を整数計画問題で表現し、その整数解として前記解を求めるようにしてもよい。
【００３９】
好ましくは、前記処理手段は、前記整数計画問題を、整数条件を実数条件に緩和して線形計画問題として解き、整数解が得られた場合に、これを求めるべき解とするようにしてもよい。
【００４０】
好ましくは、前記処理手段は、全ての不良ビットを救済できる解が存在しないことを検出する手段を有するようにしてもよい。
【００４１】
好ましくは、前記処理手段は、仮想的な予備ラインの使用の態様を変えた複数の解を求め、求められた解のうち、使用すべき現実の予備ラインの数を最小とするものを求めるべき解とするようにしてもよい。
【００４２】
好ましくは、前記処理手段は、前処理としてラインフェイルを救済する解を求める手段と、前処理において救済された不良ビットを除いた全不良ビットを、前処理において使用した仮想的な予備ラインを除いた残りの仮想的な予備ラインにより救済する解を求め、これら解を結合したものを求めるべき解とする手段とを有するように構成してもよい。
【００４３】
また、本発明は、救済対象となる半導体デバイスのメモリーブロックならびに予備ラインおよびリンボから構成される処理単位が、垂直方向の予備ラインは前記メモリーブロックの垂直方向の長さを持つ１本のラインとして垂直方向の所与のブロックに属す不良ラインに割当て可能であり且つ水平方向の予備ラインは前記メモリーブロックの水平方向の長さを持つ１本のラインとして水平方向の所与のブロックに属す不良ラインに割当て可能である、という条件を満たさない場合に、予備ラインによりメモリーブロックの不良ビットを救済する半導体不良ビット救済処理方法において、前記条件を満たすように前記処理単位を分割して形成した複数の部分処理単位夫々ごとに、予備ラインによりメモリーブロックの不良ビットを救済する解の候補を求め、前記部分処理単位夫々の解の候補を合成して前記処理単位の解を生成することを特徴とする。
【００４４】
前記部分処理単位に対する救済する解は、例えば、（１）〜（９）の方法により求めることができる。
【００４５】
好ましくは、前記部分処理単位夫々は少なくとも１つの他の部分処理単位との間で一部の予備ライン群を共用するものであり、前記部分処理単位夫々の解の候補を合成するに際しては、複数の部分処理単位間でのスペア群の共用形態を考慮して、前記処理単位の解を生成するようにしてもよい。
【００４６】
好ましくは、前記解の候補を求めるに際しては、前記複数の部分処理単位夫々ごとに所定数ずつの解の候補を求めておき、前記処理単位の解を生成するに際しては、前記部分処理単位夫々から所定の手順で１つずつ合成すべき解の候補を選択し当該解の候補の組合わせにより前記処理単位の解が得られるか否かを判断する一連の処理を繰返し行い、最初に前記処理単位の解が得られたときに当該解を採用するものとするようにしてもよい。
【００４７】
好ましくは、前記解の候補を求めるに際しては、前記複数の部分処理単位夫々ごとに所定数ずつの解の候補を求めておき、前記処理単位の解を生成するに際しては、前記部分処理単位夫々から１つずつ合成すべき解の候補を選択する全部または一部の組合わせ夫々について、当該解の候補の組合わせにより前記処理単位の解になり得るものが得られた場合にこれを前記処理単位の解の候補とし、前記処理単位の解の候補が複数得られた場合には所定の基準で選択した１つの前記処理単位の解の候補を前記処理単位の解として採用するものとするようにしてもよい。
【００４８】
好ましくは、前記部分処理単位の解の候補を合成するに際して、複数の前記部分処理単位間で共用されている予備ライン群については、当該予備ライン群を共用する部分処理単位の解の候補のうちの少なくとも１つにおいて当該予備ライン群のうちで使用不可とされたものの和集合を、当該予備ライン群における使用不可の予備ラインの集合として、当該予備ライン群に関する前記処理単位の解を求めるようにしてもよい。
【００４９】
なお、複数の前記部分処理単間で共用されていない予備ライン群については、当該予備ライン群を持つ部分処理単の解の候補における当該予備ライン群に関する部分を前記処理単位の解として採用することができる。
【００５０】
好ましくは、前記部分処理単位の解の候補を合成するに際して、使用不可の予備ライン以外の予備ラインを用いたメモリブロックの不良ビットの救済処理を、各部分処理単位について逐次的に行うとともに、当該部分処理単位の解の候補において使用不可となっている予備ラインおよびそれまでの救済処理において使用済みとなった予備ラインの和集合を当該部分処理単位における使用不可の予備ラインとして、前記処理単位の解を求めるようにしてもよい。
【００５１】
また、本発明は、救済対象となる半導体デバイスのメモリーブロックならびに予備ラインおよびリンボから構成される処理単位が、垂直方向の予備ラインは前記メモリーブロックの垂直方向の長さを持つ１本のラインとして垂直方向の所与のブロックに属す不良ラインに割当て可能であり且つ水平方向の予備ラインは前記メモリーブロックの水平方向の長さを持つ１本のラインとして水平方向の所与のブロックに属す不良ラインに割当て可能であるという条件を満たさない場合に、予備ラインによりメモリーブロックの不良ビットを救済する半導体不良ビット救済処理装置において、前記条件を満たすように前記処理単位を分割して形成した複数の部分処理単位夫々ごとに、予備ラインによりメモリーブロックの不良ビットを救済する解の候補を求める手段と、前記部分処理単位夫々の解の候補を合成して前記処理単位の解を生成する手段とを備えたことを特徴とする。
【００５２】
なお、装置に係る本発明は方法に係る発明としても成立し、方法に係る発明は装置に係る発明としても成立する。
【００５３】
また、装置に係る本発明や方法に係る本発明は、これを実現するプログラムを格納した記録媒体に係る発明としても成立する。
【００５４】
すなわち、本発明は、半導体デバイスにおけるビットデータを記憶するための第１のセルの不良ビットを予備として設けられた第２のセルにより救済する半導体不良ビット救済処理をコンピュータに実行させるプログラムであって、現実の第１のセルおよび第２のセルからなる救済対象に対して仮想的に与えた第３のセルにより、該現実の第１のセルおよび第２のセルの不良ビットを救済させる手順を有するプログラムを記録したコンピュータ読取り可能な記録媒体を要旨とする。
【００５５】
また、本発明は、半導体デバイスのメモリーブロックの不良ビットを、予備として設けられた予備ラインにより救済する半導体不良ビット救済処理をコンピュータに実行させるプログラムであって、現実のメモリーブロックならびに予備ラインおよびリンボからなる救済対象に対して仮想的に与えた予備ラインにより、該メモリーブロックならびに予備ラインおよびリンボのビット不良を救済させる手順を有するプログラムを記録したコンピュータ読取り可能な記録媒体を要旨とする。
【００５６】
また、本発明は、半導体デバイスのメモリーブロックならびに予備ラインおよびリンボの不良ビットの位置を示す情報をもとに、予備ラインによりメモリーブロックの不良ビットを救済する半導体不良ビット救済処理をコンピュータに実行させるプログラムであって、現実のメモリーブロックならびに予備ラインおよびリンボからなる救済対象に対して仮想的に与えた予備ラインにより、該メモリーブロックならびに予備ラインおよびリンボのビット不良を救済する解を求めさせ、この求められた解に基づいて、現実の予備ラインによりメモリーブロックの不良ビットを救済する解を求めさせるプログラムを記録したコンピュータ読取り可能な記録媒体を要旨とする。
【００５７】
また、他の本発明も、コンピュータに当該発明に相当する手順を実行させるための（あるいはコンピュータを当該発明に相当する手段として機能させるための、あるいはコンピュータに当該発明に相当する機能を実現させるための）プログラムを記録したコンピュータ読取り可能な記録媒体として成立する。
【００５８】
本発明では、メモリーブロックの不良ビットを予備ラインで救済する解と、メモリーブロックならびに予備ラインおよびリンボを仮想的なメモリーブロックとした場合に仮想される不良の予備ラインでこの仮想的なメモリーブロックの不良ビットを救済する解との間に一定の関係が存在することを見出だしたことにもとづき、不良ビットの存在し得る現実の予備ラインで現実のメモリーブロックの不良ビットを救済する解を直接求める代わりに、不良ビットの存在しない仮想の予備ラインで仮想のメモリーブロックの不良ビットを救済する解を求め、上記の一定の関係にもとづいて、この解から現実の解を得るものである。
【００５９】
ここで、解とは、仮想の予備ラインに関する場合、例えば次のような意味、すなわち仮想の予備ラインにより救済されるラインの集合を示す情報である。
【００６０】
また、解とは、現実の予備ラインに関する場合、例えば次のような意味、すなわち仮想の予備ラインにより救済されるメモリーブロックのラインと、そのラインの救済に使用する予備ラインとの対応を示す情報である。
【００６１】
また、解とは、現実の予備ラインに関する場合、例えば次のような意味、すなわち予備ラインにより救済するメモリーブロックのラインと、そのラインの救済に使用可能な予備ラインとを示す情報である。この場合、使用可能な予備ラインが複数存在するならば、この情報をもとに、後にリペア工程に先だって実際の対応を決定することになる。
【００６２】
より具体的には、例えば、メモリーブロックならびに予備ラインおよびリンボからなるビットマトリックス全体を対象とする、現実の予備ライン数に等しい不良ビットのない予備ラインを仮想して、解を求める。求められた解において、現実の予備ラインが仮想の予備ラインで救済されているような対応関係がある場合には、その現実の予備ラインは使用しないと解釈する。この場合、現実の予備ラインに不良ビットが存在しても、その予備ラインの割り当てに特別な扱いを必要としないので、解を求める処理が簡単になり高速化される。
【００６３】
また、仮想の予備ラインと救済される不良ラインとの対応関係の存在は、現実の予備ラインと救済される不良ラインとの対応関係の存在と、必要不十分な関係にある。これにより、仮想の予備ラインによりメモリーブロックならびに予備ラインおよびリンボからなるビットマトリックス全体を救済可能な場合は、現実の予備ラインにより現実のメモリーブロック内の全不良ビットを救済することが可能となり、一方、仮想の予備ラインの本数では該ビットマトリックス全体を救済できない場合は、現実の予備ラインによりメモリーブロック内の全不良ビットを救済することが不可能となる。
【００６４】
本発明によれば、不良ビットの存在し得る現実の予備ラインで現実のメモリーブロックの不良ビットを救済する解を直接求める代わりに、不良ビットの存在しない仮想の予備ラインで仮想のメモリーブロックの不良ビットを救済する解を求めるので、予備ラインに不良ビットが存在する場合にこの予備ラインの不良ビットを他の予備ラインで救済することを考慮しつつ解を求めるようなことが不要となり、比較的容易にかつ高速に解を求めることあるいは解が存在しないことを見地することができる。
【００６５】
また、不良ビットセルが一様に散らばって出現するような場合あるいはラインフェイルを救済した後に残った不良の多くが孤立不良のような場合などには、制限時間を超える探索を行うことが極力少なくなり、不良ラインの使用本数を最小本数またはこれに極めて近い本数で実現した不良ラインと予備ラインとの間の対応関係を求めることが多くなると期待できる。
【００６６】
また、本発明では、予備ラインを含めたメモリー全体の不良ビットセルの位置情報を２部グラフで表現して、その最大マッチングを算出することにより、配置された予備ラインの数では救済できないことを、短時間に判断できる。また、最大マッチングから算出されるＤＭ分解を用いることにより、不良ラインと予備ラインの間の最適もしくは準最適な対応関係を短時間に決定できる。特に、不良ビットセルが一様に散らばって出現しているような場合あるいはラインフェイルを救済した後に残った不良の多くが孤立不良のような場合などには、最小本数で実現した対応関係を算出することが期待できる。
【００６７】
また、本発明では、予備ラインを含めたメモリー全体の不良ビットセルの位置情報、および予備ラインの適用範囲と本数制限を整数計画問題で表現する。そして、その整数計画問題の整数条件を実数条件に緩和して得られる線形計画問題を解くことにより、実行可能解がない場合には救済不能と判定し、整数解が得られた場合は不良ラインと予備ラインの間の最適な対応関係を算出することができる。
【００６８】
また、本発明によれば、救済対象となる半導体デバイスのメモリーブロックならびに予備ラインおよびリンボから構成される処理単位が、垂直方向の予備ラインは前記メモリーブロックの垂直方向の長さを持つ１本のラインとして垂直方向の所与のブロックに属す不良ラインに割当て可能であり且つ水平方向の予備ラインは前記メモリーブロックの水平方向の長さを持つ１本のラインとして水平方向の所与のブロックに属す不良ラインに割当て可能である、という条件を満たさない場合であっても、前記条件を満たすように前記処理単位を分割して形成した複数の部分処理単位夫々ごとに、予備ラインによりメモリーブロックの不良ビットを救済する解の候補を求め、前記部分処理単位夫々の解の候補を合成することによって、前記処理単位の解を得ることができる。
【００６９】
【発明の実施の形態】
以下、図面を参照しながら発明の実施の形態を説明する。
【００７０】
本実施形態では、例えば、メモリーテスト装置により得られた不良ビットの情報（メモリーブロック内の不良ビットだけでなく予備ライン（スペア）やリンボの不良ビットの情報も含む）をもとに、メモリーブロック内の不良ビットをスペアにより救済する方法（解）を求めあるいは救済不可であることを決定し、その結果は、これをもとにレーザでヒューズを切断してスペアで救済するラインのアドレスを設定する等の工程により不良ビットを救済するリペア装置に供されるような、半導体不良ビット救済処理装置のいくつかの例について説明する。本実施形態の半導体不良ビット救済処理装置は、ソフトウエアにより実現可能であり、メモリーテスト装置やリペア装置とは独立して設けることも、メモリーテスト装置やリペア装置に内蔵することも可能であるが、以下では独立して設けるものとして説明する。なお、メモリーテスト装置からは後述するラインフェイル処理が施されていない不良ビットの情報が与えられる場合を主として説明する。また、リペア装置に供される情報として、救済の仕方（救済されるラインと使用するスペアとの対応関係）を特定した情報を出力する場合を主として説明する。
【００７１】
製造ラインにおいては、メモリーテストからリペアまでの工程は通常ロット単位（例えば、２５ウエハ／ロット、２００チップ／ウエハ）に行われるので、半導体不良ビット救済処理装置は基本的な処理単位としてはウエハ単位に動作し製造管理システムとのリンクの観点ではロット単位に稼働することが多い。一方、オフラインにおいては、半導体不良ビット救済処理装置は、ロット単位からメモリーブロック単位まで任意に使用可能なことが多い。しかし、いずれの場合においても、半導体メモリーの１チップは通常、同様の構成を有する複数のメモリーブロック（例えば４×８個）からなり、不良ビットの救済のためのスペアとリンボはメモリーブロックごとに設けられるので、本実施形態に係る不良ビット救済処理は、このメモリーブロック単位に行われることになる。以下では、１つのメモリーブロックに対する処理を中心に説明していく。
【００７２】
本発明は、どのような構成を有する半導体メモリーあるいはメモリーを有する他のデバイスにも適用可能であるが、最初に、本実施形態を説明するために一例として用いる半導体メモリー（以下、ＲＡＭとする）の不良ビット救済に関する構成について説明する。
【００７３】
図１に、本実施形態に係る半導体不良ビット救済処理装置が処理対象とするＲＡＭの内部のメモリーブロック２００と予備ライン（以下、スペアと呼ぶ）２１１〜２１４とリンボ２１５〜２１８の配置図の一具体例を示す。メモリーブロックの行方向のビット数や列方向のビット数が任意であるが、もちろん、メモリーブロックの行方向のビット数と水平のスペアのビット数は同一であり、メモリーブロックの列方向のビット数と垂直のスペアのビット数は同一である。また、リンボは、１つの水平のスペアと１つの垂直のスペアの組ごとに対応して１ビットずつ設けられる。
【００７４】
図１のＲＡＭでは、１つのメモリーブロック２００を上下に２分割と左右に２分割した（全体として４分割した）サブブロックを考える（図１中の点線が分割の境界を示す）。つまり、図中のサブブロックＢＬＫ１（図中の左上の四半分２０１）、ＢＬＫ２（図中の左下の四半分２０２）、ＢＬＫ３（図中の右上の四半分２０３）、ＢＬＫ４（図中の右下の四半分２０４）の集まりが１つのメモリーブロックに対応する。
【００７５】
メモリーブロックの上、下、左、右には、それぞれ、３本、３本、６本、６本のスペア２１１，２１２，２１３，２１４が配置されている。
【００７６】
４角にある３×６の行列２１５，２１６，２１７，２１８の要素は、リンボ（ｌｉｍｂｏ）と呼ばれるメモリーセルであり、救済に使用した水平方向のスペアと垂直方向のスペアとの交点に位置するビットを代替するものである。詳しくは後述するように、リンボに不良ビットがある場合、スペアの使用に制約（リンボに関する制約）を与えることになる。
【００７７】
図１中の×印は不良ビットを表している。
【００７８】
以下では便宜上、メモリーブロック行列のＢＬＫ１とＢＬＫ３を合せたものをメモリーブロック行列の上行と呼ぶ。同様に、ＢＬＫ２およびＢＬＫ４、ＢＬＫ１およびＢＬＫ２、ＢＬＫ３およびＢＬＫ４を、それぞれ、メモリーブロック行列の下行、左列、右列と呼ぶ。
【００７９】
また、メモリーブロックの上、下、左、右にあるスペアを、それぞれ、上水平スペア（図１ではＣ１〜Ｃ３）、下水平スペア（図１ではＣ４〜Ｃ６）、左垂直スペア（図１ではＲ１〜Ｒ６）、右垂直スペア（図１ではＲ７〜Ｒ１２）と呼ぶ。
【００８０】
ここで、図１に例示したＲＡＭのメモリーブロックにおいては、各ＢＬＫｉ（ｉ＝１〜４）の救済方法には次のようなスペアに関する制約があるものとする。
・ＢＬＫ１の不良ビットは上水平スペアまたは左垂直スペアによってのみ救済可能である。
・ＢＬＫ２の不良ビットは下水平スペアまたは左垂直スペアによってのみ救済可能である。
・ＢＬＫ３の不良ビットは上水平スペアまたは右垂直スペアによってのみ救済可能である。
・ＢＬＫ４の不良ビットは下水平スペアまたは右垂直スペアによってのみ救済可能である。
【００８１】
なお、この制約は図１のＲＡＭの持つ構成に固有のものであり、このようなスペアに関する制約は半導体メモリーの構成に応じて与えられるものである（半導体メモリーによってはこのような制約がない場合もあり得る）。
【００８２】
また、図１の場合、上水平スペアについては３本、下水平スペアは３本、左垂直スペアは６本、右垂直スペアは６本が、それぞれ、使用可能な上限本数となる。通常、水平方向や垂直方向のスペアの数は、メモリーブロックの行や列の数よりも少ないので、使用可能なスペアの上限本数の制約は一般的に存在する。
【００８３】
さらに、本発明では、リンボを持つ半導体メモリーを想定しているが、この場合、リンボに関する制約が一般的に存在する。詳しくは後述するが、リンボが不良ビットであると、このリンボに対応する水平方向のスペアと垂直方向のスペアのいずれか一方しかメモリーブロックの救済に使用できないという制約が課される。従って、図１のＲＡＭの場合も、リンボに関する制約が課される。
【００８４】
さて、本実施形態に係る半導体不良ビット救済処理装置では、スペアに関する制約およびリンボに関する制約のもとで、メモリーブロックにおける不良ライン（行あるいは列）をスペアで置き換えて救済する解を求める処理を行う。そして、リペア装置では、この解に従って、メモリーブロックにおける不良ライン（行あるいは列）をスペアで置き換えるために、レーザでヒューズを切断してアドレスを設定する等のプロセスを行う。この置き換えのためのプロセスにはコストがかかるため、通常、得られた救済方法の良し悪しを判断するための評価基準が定義される。本実施形態では、救済のために使用するスペアの総数を評価基準に用いるものとする。つまり、使用するスペアの総数が少ないほど、良い救済方法であると解釈する。このような不良救済問題の実行可能解を「救済解」と呼び、スペア数を最小とする救済解を「最適な救済解」と呼ぶ。また、救済解に用いられるスペアを「救済ライン」と呼ぶ。また、救済解無しの場合を「救済不可」と呼ぶことがある。なお、救済不可には、メモリーブロックに存在する全ての不良ビットを救済可能なスペアの組合せが得られなかった場合の他に、処理時間の制限を設ける場合で、救済解が得られるまでに制限時間に達してしまった場合がある。
【００８５】
なお、本実施形態では、ある処理単位について１つの救済解が得られた時点または救済不可が決定された時点で、次の処理単位の救済処理に進む形態を中心に説明するが、いくつかの救済解を求め、上記評価基準に基づく評価関数により、より良い救済解を選択して出力するようにすることも可能である。
【００８６】
図２に図１と同様の構造を有するメモリーブロックの不良ビットを救済する一例を示す。なお、この例では簡単のためブロックのサイズやスペアの本数を小規模にしてある。
【００８７】
図２中では、不良ビットを１で、正常ビットを０で表す。この表記の仕方は、以下で参照する他の図においても同様である。
【００８８】
図２の例の場合、ある救済解においては、図中の矢印の始点にあるスペアが終点にある行ラインや列ラインを代替する。この救済解は最適な救済解であり、その救済ライン数は３である。例えば、他の救済方法として、ＢＬＫ４の２つの不良ビットについては右垂直スペアを２本用いることによっても救済可能であるが、この場合は計４本のスペアを要することになり最適解にはならない。
【００８９】
上記した図２の例は、メモリーブロックのみに不良ビットが存在し、スペアおよびリンボには不良ビットが存在しない例であったが、一般にはスペアやリンボにも不良ビットが存在し得る。
【００９０】
もし救済ラインの候補であるスペアに不良ビットがある場合は、そのスペアに直交するスペアを使用してそのスペアの不良ビットをも救済することが可能である。リンボ行列はその際に使用可能な直交スペアの情報を与えるものである。以下、図１の例を用いてリンボ行列の役割について説明する。ここでは、左上端のリンボ行列を取り上げて説明するが、他の３つのリンボ行列についてもその役割は同様である。
【００９１】
まず、左上端のリンボ行列の（ｉ，ｊ）成分を便宜上、（ｉ，ｊ）リンボと呼ぶことにする。ここで、１≦ｉ≦３，１≦ｊ≦６である。
【００９２】
この（ｉ，ｊ）リンボが不良である場合、対応する上水平スペアＣｉ  と左垂直スペアＲｊ  のうち、いずれか一方のみが使用可能となる（つまり両方は使用できない）。
【００９３】
一方、この（ｉ，ｊ）リンボが良の場合（つまり不良でない場合）は、対応する上水平スペアＣｉ  と左垂直スペアＲｊ  とが併用可能となる（つまりいずれか一方を使用することも両方を使用することも可能となる）。
【００９４】
なお、（ｉ，ｊ）リンボは、両スペアＣｉ  ，Ｒｊ  を実際に使用した際の交点の代用メモリーセルとして使用される。従って、もし（ｉ，ｊ）リンボが良ならば、両スペアＣｉ  ，Ｒｊ  を実際に使用した際の交点に不良が存在（残存／発生）しても構わないことになる。
【００９５】
このようにスペア上に存在する不良ビットは、そのスペアに直交する他のスペアでのみ救済が可能であるが、そのような救済を行う場合、この２つのスペアの組に対応するリンボは良でなければならない。また、スペア上に存在するビット不良を実際に救済するのは、代用メモリーとしてのリンボの成分であって、直交するスペアの成分ではない。
【００９６】
図３に図２と同じ構成のメモリーブロックにおいてリンボやスペアに不良が存在する場合の一例を示す。なお、この例でも簡単のためブロックのサイズやスペアの本数を小規模にしてある。この例の場合、ある救済解においては、図中の矢印の始点にあるスペアが終点にある行や列を代替する。この救済解は最適な救済解であり、救済ライン数は４である。図３の場合、例えば最右の垂直スペアは上水平スペアの不良を救済している（実際には対応するリンボの成分により救済される）。
【００９７】
なお、図１におけるスペアの本数やリンボのサイズは一例であり、本発明を実施するにあたってこれらの数値は本質的ではない。また、図１の構造（すなわち、メモリーブロックの上、下、左、右にスペアが配置され、メモリーブロックが４つのＢＬＫｉに４分割され、各ＢＬＫｉの救済に使用可能なスペアの位置等に対する制約を持つなどの構造）自体も一例であり、本発明は種々の構造を持つ半導体メモリーに適用可能である。例えば、メモリーブロックが４分割される場合だけでなく、８分割される場合、いずれかの方向のみに２分割される場合、分割されない場合（スペアのサブブロックへの適用制限がない場合）など、スペアの位置がメモリーブロックの上、下、左および右とは相違する場合、スペアの使用に他の制限が課される場合など、種々の構造を持つ半導体メモリーに適用可能である。もちろん、半導体メモリーもＲＡＭに限らず、種々のデバイスに適用可能である。
【００９８】
次に、本発明に係る救済処理（問題解法）の基本原理等について説明する。
【００９９】
以下、メモリーブロック行列（スペアとリンボを含まないもの）を行列Ａで表すものとする。一方、図４に示すように、（ａ）に示すような行列Ａにスペアとリンボ（図示せず）を全て添付して得られる（ｂ）に示すような行列を考える。以下、このような行列を行列Ｂで表すものとする。例えば、図１の２００のメモリーブロックが行列Ａに該当し、図１をまとめて１つの行列と考えたものが行列Ｂに該当する。
【０１００】
行列Ｂの上行、下行、左列、右列は、行列Ａの場合と同様に定義する。例えば、図１の水平な点線の上部、下部がそれぞれ行列Ｂの上行、下行であり、垂直な点線の左側、右側がそれぞれ行列Ｂの左列、右列である。
【０１０１】
さらに、本発明では、行列Ｂに対して、行列Ａのスペアの数と同数でかつ行列Ａと同様の制約を持つ、不良のない新たなスペアを仮想する。例えば、図１の行列Ｂの上下にはそれぞれ３本ずつ、左右にそれぞれ６本ずつの「不良ビットのないスペア」が存在しているものと仮定する。なお、行列Ｂのスペアには不良がないと仮定するので、ここでは行列Ｂに対するリンボは不要である。また、このような仮想したスペアにはリンボに関する制約がないものとする。
【０１０２】
なお、スペアについての混同を避けるために、行列ＡにおけるスペアをＡスペア、行列Ｂにおいて仮想したスペアをＢスペアと呼んで明示的に両者を区別することがある。
【０１０３】
次の定理は、行列Ａの救済解と行列Ｂの救済解の間の対応関係を示すものであり、本来の不良救済という問題を行列Ｂに拡張することの正当性を保証するものである。
【０１０４】
（定理）
「行列Ａの救済解が存在するための必要十分条件は、行列Ｂの救済解が存在することである。」
（必要性の証明）
まず、必要性の証明を示す。
Ａの救済ライン集合をＬ（Ａ）とする。Ｂの行、列ベクトルのうち、Ａの要素を含まない行、列ベクトルの全体をＸとする（つまり、Ａの外側にあるＢの行、列ベクトルの全体からなる集合をＸとする）。また、Ｌ（Ａ）の各行、各列を延長して得られるＸの部分集合をＬ（Ａ）ｅ  とし、Ｌ（Ａ）によって救済される行列Ａの行、列を延長して得られる行、列の集合をＬ′（Ａ）ｅ  とする。
【０１０５】
図５にその具体例を示す。図５では、１，２，…，７のラインがＬ（Ａ）ｅ  に、１′，２′，…，７′のラインがＬ′（Ａ）ｅ  にそれぞれ該当し、ｉＡ  がｉ′Ａ  を救済する（ｉ＝１，２，…，７）。ただし、ｉＡ  ，ｉ´Ａ  等の添字ＡはＡの高さまたは幅への制限を表す。
【０１０６】
このとき、Ｂ−Ａに属する不良は、Ｌ′（Ａ）ｅ  またはＸ−Ｌ（Ａ）ｅ  のライン上に存在することが示せる。具体的には、Ｌ（Ａ）ｅ  のライン上にあってＬ′（Ａ）ｅ  のライン上にはない成分についてチェックすればよい：
（ｉ）Ｌ（Ａ）ｅ  の、互いに直交する２本のラインの交点：これは良のリンボなので正常である。
【０１０７】
（ｉｉ）Ｌ（Ａ）ｅ  上の（ｉ）以外のリンボ：不良があった場合は、直交するＸ−Ｌ（Ａ）ｅ  のライン上に存在する。
【０１０８】
（ｉｉｉ  ）Ｌ（Ａ）−Ｌ′（Ａ）ｅ  上の成分：不良は有り得ない（不良があるとすると、それを救済するＡの直交スペアが必要になるので、結局Ｌ′（Ａ）ｅ  に属してしまい矛盾する。）
【数１】
0003581249.tif 000002
【０１０９】
従って、式（１）で表されるＬ（Ｂ）は行列Ｂの不良を全てカバー（救済）していることが分かる。
【０１１０】
さらに、Ｌ（Ｂ）がカバーする行列Ｂの上行、下行、左列、右列のライン数はそれぞれ上水平、下水平、左垂直、右垂直のＢスペア数以下（実際は等しい）なので、このＬ（Ｂ）はＢの救済ライン集合を与える。
（必要性の証明の終り）
（十分性の証明）
次に、十分性の証明を示す。
Ｂの救済ライン集合をＬ（Ｂ）とする。Ｌ（Ｂ）でカバーされていないＡスペアの集合をＬｏ  （Ａ）とする。Ｌ（Ｂ）によってカバーされているＡの行、列の集合をＬＡ  とする。
【０１１１】
図６にその具体例を示す。図６では、１´，２´，…，８´のラインがＬ（Ｂ）に該当し、２´Ａ  ，６´Ａ  ，７´Ａ  ，８´Ａ  がＬＡ  にそれぞれ該当する。ただし、２´Ａ  等の添字ＡはＡの高さまたは幅への制限を表す。
【０１１２】
ＬＡ  をカバーしている上水平、下水平、左垂直、右垂直のＢスペアの本数をそれぞれｕ，ｄ，ｌ，ｒとすると、Ｌｏ  （Ａ）には、上水平、下水平、左垂直、右垂直のスペアがそれぞれ少なくともｕ，ｄ，ｌ，ｒ本は存在する。それらを該当する本数だけ（つまりｕ，ｄ，ｌ，ｒずつ）任意にピックアップして得られるＬｏ  （Ａ）の部分集合をＬ（Ａ）とすると、Ｌ（Ａ）はＡを救済する。
【０１１３】
図６の２Ａ  ，６Ａ  ，７Ａ  ，８Ａ  がＬ（Ａ）の例である。
【０１１４】
これを示すために、まずＬＡ  のラインとＬ（Ａ）のスペアとの間に任意に一対一対応をつけておく（但しＡの上部には上水平のスペアを対応させる等の条件は満たすものとする）。さて、Ｌ（Ａ）のライン（ｋとする）上に不良がある場合、その不良はＬＡ  のラインの延長上にある（その理由は、不良はＬ（Ｂ）のラインでカバーされるからである）。そのラインに対応するＬ（Ａ）のラインをｈとすると、ｋ，ｈを延長したときの交点（リンボ）はＬ（Ｂ）のどのラインにもカバーされないため正常（良）である。つまり、このリンボによって、前記の不良は解消される。すなわち、Ｌ（Ａ）のライン上の不良はＡをカバーした際、全て解消される。従って、上記の一対一対応のもとでＬＡ  の各ラインにＬ（Ａ）のスペアを割当ててやればＡが救済される。
（十分性の証明の終り）
なお、この定理は、図１で例示した構造（すなわち、メモリーブロックの上、下、左、右にスペアが配置され、メモリーブロックが４つのＢＬＫｉに４分割され、各ＢＬＫｉの救済に使用可能なスペアの位置等に対する制約を持つなどの構造）のみならず、どのような構造を持つメモリーブロックについても成立する。すなわち、メモリーブロックの分割数やスペアの配置場所には依存せずに成立する。
【０１１５】
この定理の実用上の意義は、上記証明の中に示されている。つまり、行列Ａの救済ライン集合Ｌ（Ａ）で救済されるＡの不良ラインの集合は、行列Ｂの救済ライン集合で救済されるＢの不良ラインの集合へと自然に拡張することができる。逆に、Ｂの救済ライン集合Ｌ（Ｂ）によってカバーされているＡの各不良ラインに対して、Ｌ（Ｂ）によってカバーされていないＡのスペアを任意に対応させることが可能であり、従ってＬ（Ｂ）からＡの救済解を構成することができる。
【０１１６】
本発明に係る半導体不良ビット救済処理装置は、この点に基づいて救済解を求めるものである。
【０１１７】
以下では、本発明の実施の形態に係る半導体不良ビット救済処理装置の基本構成について説明する。
【０１１８】
本実施形態に係る半導体不良ビット救済処理装置は、上記定理に基づいたもので、概略的には、まず、与えられたメモリーブロック、スペアおよびリンボの不良ビットのアドレス情報および処理対象となるＲＡＭに応じたスペアに関する制約をもとに、行列Ｂ（メモリーブロック、スペアおよびリンボからなる行列）の救済解を求める。救済解としては、救済される行列Ｂの行アドレスおよび列アドレス（いずれか一方の場合もある）の番号が与えられる。
【０１１９】
ここで、行列ＢにおいてＢスペアにより救済される行ラインや列ラインには、メモリーブロック（すなわち行列Ａ）の要素を含むものと含まないものとがある。その中で、メモリーブロックの要素を含むライン（の行または列アドレス）は、行列Ａで救済される行や列を与える。また、メモリーブロックの要素を含まないライン（の行または列アドレス）は、行列Ａに対する現実のスペア（Ａスペア）のうち使用できないものを与える（つまり、その他のＡスペアが使用可能であることになる）。
【０１２０】
次に、行列Ｂの救済解をもとに、行列Ａすなわちメモリーブロックに対する救済解を求める。すなわち、Ｂスペアによってカバーされているメモリーブロックの各不良ラインに対して、ＢスペアによってカバーされていないＡスペアを任意に対応させることにより、Ａの救済解を構成する。
【０１２１】
図７に本実施形態に係る半導体不良ビット救済処理装置の基本構成を示す。この半導体不良ビット救済処理装置は、入力処理部１、ラインフェイル処理部２、救済処理部３、出力処理部４を備えている。図８にこの半導体不良ビット救済処理装置の処理手順の一例を示す。
【０１２２】
入力処理部１は、ステップＳ１において、メモリーテスタ装置からの不良ビットのアドレス情報（行アドレスと列アドレスの対）を入力し、格納する。この情報は、行列Ｂとして保持される。
【０１２３】
ラインフェイル処理部２は、ステップＳ２において、ラインフェイル処理を行い、行列Ｂを縮小する。ラインフェイルとは、あるラインについて、不良ビットが多数存在するために必然的にスペアの割り当てが決まる状態を言う。例えば、図１の構造において、行列Ｂの上行に属する行ラインの左列に属する成分に、左垂直スペアの残数を上回る不良ビットが存在した場合は、それらの不良は左垂直スペアでは救済不能なため、当該ＲＡＭを救済するためには、上水平スペアで救済せざるを得ない。このような状態がラインフェイルである。なお、この例の場合に上水平スペアの残数が０ならば、当該ＲＡＭは救済不可となる。ラインフェイル処理は、入力処理部１の処理と同時におよび／またはその処理の終了後に行われる。
【０１２４】
救済処理部３は、ステップＳ３において、所定の手順により、行列Ｂに対する救済解を求める。あるいは、救済不可を判断する。
【０１２５】
出力処理部４は、ステップＳ４において、行列Ｂに対する救済解から行列Ａに対する救済解を求めて、これを出力する。また、ラインフェイル処理部２もしくは救済処理部３において救済不可と判定された場合、その旨を示すメッセージを出力する。
【０１２６】
ここで、図９〜図１１の簡単な具体例を用いて不良ビット救済処理について説明する。
【０１２７】
図９に図１と同様の構造を有するメモリーブロックの一例を示す。この例では、メモリーブロックは４行×４列で、上水平スペア、下水平スペア、左垂直スペア、右垂直スペアはそれぞれ１本、１本、２本、２本設けられている。また、図９において、Ｌ１〜Ｌ６は、それぞれ、行アドレスが１〜６のラインを示し、Ｃ１〜Ｃ８は、それぞれ、列アドレスが１〜８のラインを示す。
【０１２８】
図９の例の場合、不良ビットのアドレス情報を（行アドレス、列アドレス）の形式で表すと、（１，６），（１，７），（３，３），（４，４），（５，２），（５，５），（５，６），（５，７），（５，８），（６，１），（６，４）の情報が入力される。
【０１２９】
図１０に、図９の例に対応する救済解の一例を示す。この場合、Ｌ５とＣ４がラインフェイルとなる。図１０では、Ｂスペアによって救済される行列Ｂのラインは、Ｌ３，Ｌ５，Ｃ１，Ｃ４，Ｃ６，Ｃ７となる。
【０１３０】
これにより、救済される行列Ａのラインは、Ｌ３，Ｌ５，Ｃ４，Ｃ６となり、救済に使用可の行列Ａに対するスペアは、Ｌ１，Ｌ６，Ｃ２，Ｃ８（救済に使用不可の行列Ａに対するスペアは、Ｃ１，Ｃ７）となる。
【０１３１】
そして、任意に対応付けを行うと（ただし、この例の場合は対応付けの自由度はない）、行列ＡのラインＬ３をＬ１のスペアで救済し、ラインＬ５をスペアＬ６で救済し、ラインＣ４をスペアＣ２で救済し、ラインＣ６をスペアＣ８で救済する解が得られる。この様子を図１１に示す。
【０１３２】
以上のようにして救済解を求めることができる。
【０１３３】
ここで、いくつかの変形例について説明する。
【０１３４】
不良ビットの分布状況等によっては非常に簡単に（簡易な処理により）救済解を求めることができる場合がある。例えば、不良ビット総数が少ない場合、あるいはラインフェイルを除いた不良ビット総数が少ない場合、あるいはスペアやリンボには不良ビットがなく、メモリーブロック内の不良ビット数も少ない場合、あるいはメモリーブロック内の不良ビット数が微小の場合など、種々の場合が考えられる。例えば、極端にいえば、スペアに不良がなくメモリーブロック内の不良ビットが１つのみである場合、この不良ビットを救済対象とする任意のスペアを１つ選択するだけでよい。このような場合に、例えば、図１２や図１３に示すように救済処理部３の他に不良ビットの分布状況等が予め規定された条件を満たす場合に該予め規定された条件に対応した簡易処理を行う簡易処理部６をも備え、ラインフェイル処理の前および／または後に前処理部５で簡易処理可能か否か判定し、簡易処理可能と判定された場合には、簡易処理を行うようにしてもよい。
【０１３５】
また、１つのメモリーブロックに対する処理時間の制限を設定し、この制限時間内に救済解が得られなかった場合には、救済不可と判定するようにしてもよい。
【０１３６】
また、ラインフェイル処理は、メモリーテスタ装置の方で行い、ラインフェイルのビット不良を除いたアドレス情報と、ラインフェイルにより救済するラインのアドレスとを入力するようにしても良い。さらに、ラインフェイル処理を、メモリーテスタ装置側でも本半導体不良ビット救済処理装置側でも行わないようにして構わない。
【０１３７】
また、本半導体不良ビット救済処理装置側（出力処理部４）では、行列Ｂの救済解をもとに、救済する不良ラインと使用するＡスペアとの対応までは特定せずに、メモリーブロックで救済する全不良ラインと各不良ラインに使用可能なＡスペアとを示す情報（広い意味での救済解）を求めて出力し、リペア装置の方で最終的な対応を決定するようにしてもよい。
【０１３８】
以下では、より詳しい実施形態、特に上記のラインフェイル処理や救済処理についてより詳しく示した実施形態をいくつか説明する。まず、救済処理としてグラフ理論を利用したものを説明し、次に救済処理として線形計画法を利用したものを説明し、さらに種々の構成・変形例等について説明する。
【０１３９】
まず、本発明のより詳しい第１の実施形態に係る半導体不良ビット救済処理装置について説明する。
【０１４０】
図１４は、本実施形態に係る半導体不良ビット救済処理装置の概略構成を示すブロック図である。
【０１４１】
この半導体不良ビット救済処理装置は、データ入力部１０、ラインフェイル判定部２０、２部グラフ作成部３０、最大マッチング作成部４０、ＤＭ分解作成部５０、救済解作成部６０、救済結果出力部７０を備えている。
【０１４２】
データ入力部１０は、ＲＡＭのメモリーブロック、スペアおよびリンボの不良ビットに関する情報を読み込む。
【０１４３】
ラインフェイル判定部２０は、不良数の多いラインへの必然的なスペア割当てを行う。また、ラインフェイル判定部２０では、行列の各ブロック（行列Ｂの上部と左部の重複部分等）のサイズによって必然的に決まる救済不能の判定も行う。
【０１４４】
２部グラフ作成部３０は、ラインフェイル判定部２０を経て縮小された不良ビットデータをもとに２部グラフを作成する。
【０１４５】
最大マッチング作成部４０は、作成された上記２部グラフの最大マッチングを求める。また、この最大マッチングをもとに救済不可の判定を行う。
【０１４６】
ＤＭ分解作成部５０は、求められた上記最大マッチングのデータを用いてＤＭ分解およびその縮約グラフを求める。
【０１４７】
救済解作成部６０は、上記のＤＭ分解およびその縮約グラフにもとづいて、不良ラインとスペアの間の対応関係を決めるとともに、救済不可を検出する。
【０１４８】
救済結果出力部７０は、救済解が得られた場合には本来のメモリーブロックの不良ラインと本来のスペアとの間の対応関係を求めて出力する。一方、ラインフェイル判定部２０、最大マッチング作成部４０もしくは救済解作成部６０において、スペアの本数に関する制限を満たす救済解が存在しないことが判明した場合、または制限時間内に救済解が得られず時間切れとなった場合には、「救済解が存在しない」旨を示すメッセージを出力する。なお、救済解が得られなかった場合、後の解析等の処理のために、どの処理において時間切れ以外の理由で救済不可となったかあるいはどの処理の時点で時間切れとなったかを示す情報を出力するようにしてもよい。
【０１４９】
なお、行列Ａから行列Ｂへの拡大操作は、データ入力部１０において、メモリーブロック、スペアおよびリンボの不良ビットを読み込んだ後、それらの不良ビット間に区別を設けずに同等に扱うことで、実質的に拡大操作が行われる。ラインフェイル判定部２０から救済解作成部６０に至る過程は、拡大行列Ｂに対する操作である。救済結果出力部７０において初めて、本来のメモリーブロック行列Ａの不良ラインと本来のスペア（Ａスペア）を区別して、両者の間の対応関係を算出するという操作を行う。
【０１５０】
次に、本実施形態に係る半導体不良ビット救済処理装置の処理手順について詳しく説明する。図１５は、本実施形態の半導体不良ビット救済処理装置の処理手順の一例を示すフローチャートである。
【０１５１】
ここでは、図１で説明した構造を持つＲＡＭの内部のある１つのメモリーブロックに対するメモリーテストの結果、図１６の行列Ｂ（メモリーブロック、スペア、リンボ）で示されるような不良ビットについて、不良ビットの情報が入力された場合を具体例として取り上げて説明する。
【０１５２】
図１６に示されるように、この具体例に係るＲＡＭのメモリーブロックは、２４行×２４列（行アドレス１〜３，２８〜３０と列アドレス１〜３，２８〜３０を除く部分）で構成され、上水平スペア（行アドレス１〜３に対応）、下水平スペア（行アドレス２８〜３０に対応）、左垂直スペア（列アドレス１〜３に対応）、右垂直スペア（列アドレス２８〜３０に対応）がそれぞれ３本ずつと、４隅にこれらスペアに対応する計３６個のリンボが設けられている。また、前述したようなスペアに関する制約、すなわち、メモリーブロックの左上の四半分は上水平スペアまたは左垂直スペアによってのみ救済可能であり、同様に、メモリーブロックの左下、右上、右下の各四半分は、それぞれ、下水平スペアまたは左垂直スペア、上水平スペアまたは右垂直スペア、下水平スペアまたは右垂直スペアによってのみ救済可能であるという制約があるものとする。また、前述したようなリンボに関する制約がある。なお、図１６中、１は不良ビットを、０は正常ビットを表す。
【０１５３】
前述したように、本実施形態では、まず、行列Ｂ（メモリーブロック、スペア、リンボ）の不良ビットを救済する解を求めるが、その際、行列Ａの救済と同様のスペアに関する制約を課すことになる。すなわち、行列Ｂに対して、不良ビットのない仮想の上水平スペア、仮想の下水平スペア、仮想の左垂直スペア、仮想の右垂直スペアをそれぞれ３本ずつ使用可能とする。また、行列Ｂの左上、左下、右上、右下の各四半分は、それぞれ、仮想の上水平スペアまたは仮想の左垂直スペア、仮想の下水平スペアまたは仮想の左垂直スペア、仮想の上水平スペアまたは仮想の右垂直スペア、仮想の下水平スペアまたは仮想の右垂直スペアによってのみ救済可能であるという制約があるものとする。なお、前述したように仮想のスペアに対応する仮想のリンボは以下の処理では使用しない。
【０１５４】
（１）まず、ステップＳ１０１の、データ入力部１０により不良ビットのアドレスデータを読み込んで、これを行列Ｂに拡張する処理について説明する。
【０１５５】
ステップＳ１０１では、ＲＡＭのメモリーブロック、スペアおよびリンボにおける不良ビットの位置を示す行のアドレスと列のアドレスとの対からなるデータを逐次入力する。このデータは、
ｒｏｗ：整数  ｃｏｌｕｍｎ：整数
という形式で記述されるものとする。
例えば、行アドレス１２０、列アドレス４５のセルに不良ビットが存在する場合には、ｒｏｗ：１２０，ｃｏｌｕｍｎ：４５という形式で記述される。このデータは、行アドレスまたは列アドレスによって予めソートされているものとする。図１６の行列Ｂに対応する入力データの例を図１７に示す。
【０１５６】
なお、入力データの形式は、上記したもの以外の形式でも構わない。例えば、行列Ｂの全ビットマップのデータ（行アドレス、列アドレス、良または不良を示すビット等）を入力してもよい。
【０１５７】
また、ステップＳ１０１では、内部で保持する各種データを初期化する。例えば、図１６の例の場合、図１８（ａ）に示すように、上水平スペア、下水平スペア、左垂直スペア、右垂直スペアの残数をそれぞれ３本に設定する。
【０１５８】
本実施形態では、垂直スペアを優先して使用するか、水平スペアを優先して使用するか、を予め指定するものとする。後述するステップＳ６０２とＳ６０３では、垂直スペア優先の場合と、水平スペア優先の場合とで、動作が少しことなる。
【０１５９】
ところで、このステップＳ１０１におけるデータの入力はまとめて行い、全データを格納してから、ラインフェイルの処理を行ってもよいが、本実施形態ではステップＳ１０１で１つの不良ビットのデータを入力するごとに、次のラインフェイルの処理（データ格納を含む）を行うものとする。したがって、次のステップＳ２０１は、これを前提として説明する。
【０１６０】
（２）次に、ステップＳ２０１のラインフェイル判定部２０による第１のラインフェイル検出処理について説明する。
【０１６１】
前述したように、ラインフェイルとは、あるラインについて、不良ビットが多数存在するために必然的にスペアの割り当てが決まる状態を言う。例えば、図１６において、行列Ｂの上行に属するラインの左列に属する成分に、左垂直スペアの残数を上回る不良ビットが存在した場合は、それらの不良は左垂直スペアでは救済不能なため、当該ＲＡＭを救済するためには、上水平スペアで救済せざるを得ない。このような状態がラインフェイルである。なお、この例の場合に上水平スペアの残数が０ならば、当該ＲＡＭは救済不可となる。
【０１６２】
ステップＳ２０１では、行アドレスまたは列アドレスによってソートされた順に入力される不良ビットのアドレスをその入力順にチェックしていき、同じ行アドレスか同じ列アドレスが連続して出現する場合は、その出現回数をカウントし、この連続して出現した回数とその行アドレスまたは列アドレスに対応するスペアの残数とを比較することによって、ラインフェイルか否かを判定する。
【０１６３】
ラインフェイルでない場合は、そのデータを入力データ格納用ファイルに書き込む。
【０１６４】
ラインフェイルと判定された場合は、その行または列のラインに属する不良ビットは、入力データ格納用ファイルから全て削除するとともに、以後は当該ラインに属する不良ビットは入力データ格納用ファイルには書き込まないようにする。また、その行または列のラインを記憶するとともに、ラインフェイルに割り当てるべく、対応するスペアの残数を１減らす（すなわちスペアを１本割り当てたと解釈する）。
【０１６５】
例えば、図１７の入力データの場合、
ｒｏｗ：  １  ｃｏｌｕｍｎ：  ２から
ｒｏｗ：  ７  ｃｏｌｕｍｎ：１７まではラインフェイルではないと判定されるので、これらデータを入力データ格納用ファイルに書き込み、さらに、
ｒｏｗ：１０  ｃｏｌｕｍｎ：  ７
ｒｏｗ：１０  ｃｏｌｕｍｎ：２４
ｒｏｗ：１０  ｃｏｌｕｍｎ：２５
ｒｏｗ：１０  ｃｏｌｕｍｎ：２６
をこの順番に読み込んで、入力データ格納用ファイルに書き込んだ後、
ｒｏｗ：１０  ｃｏｌｕｍｎ：２７
を読み込むと、この時点で行アドレス１０の行がラインフェイルと判定される  （右垂直スペアは３本しかないからである）。従って、ｒｏｗを１０とする上記の４つのアドレスデータは入力データ格納用ファイルから削除され、
ｒｏｗ：１０  ｃｏｌｕｍｎ：２７
は、入力データ格納用ファイルには書き込まれない。
また、次に読み込むデータ
ｒｏｗ：１０  ｃｏｌｕｍｎ：２８
も、入力データ格納用ファイルには書き込まれないことになる。
【０１６６】
この結果、行アドレス１０のラインフェイルには上水平スペアが割り当てられるので、上水平スペアの残数を１本減らして残数２とする。また、ラインフェイルとして行アドレス１０を記憶する。
【０１６７】
さて、前述したようにステップＳ１０１とＳ２０１は、不良ビットのデータを１つ読み込む毎に実行するものとした。このときのステップＳ１０１およびＳ２０１の処理手順の一例を図１９に示す。
【０１６８】
また、本ラインフェイル処理において、対応するスペアが不足してラインフェイルが救済できない場合は、当該ＲＡＭを救済できないので、その時点で異常終了とし、ステップＳ７０２に進む。
【０１６９】
ここで、図１７にステップＳ１０１，Ｓ２０１のサイクルを適用すると、結局、ラインフェイルと判定された行アドレス１０のラインに属する６つの不良ビット以外の計２２個の不良ビットのアドレスのデータが、入力データ格納用ファイルに書き込まれる。また、図１８（ｂ）に示すように、上水平スペア、下水平スペア、左垂直スペア、右垂直スペアの残数はそれぞれ２本、３本、３本、３本に更新され、図１８（ｃ）に示すように、ラインフェイルとして行アドレス１０が記憶される。なお、図１８中で、ｒｎは行アドレスｎを示し、ｃｍは列アドレスｍを示すものとする。また、仮想の上水平スペアにより救済される行列Ｂにおける行アドレス１０のラインを図２０中に「ラインフェイル（その１）」として示す。
【０１７０】
（３）次に、ステップＳ２０２のラインフェイル判定部２０による第２のラインフェイル検出処理について説明する。
【０１７１】
ステップＳ２０２では、ステップＳ１０１，Ｓ２０１のサイクルの終了後、入力データ格納用ファイルに書き込まれているデータを参照して、各アドレスについて同一アドレスを持つ不良ビットの総和を計算し、それぞれ対応するスペアの残数と比較することによって、再度、ラインフェイルの検出を行う。ラインフェイルが検出された場合は、そのラインに属する不良ビットは、入力データ格納用ファイルから全て削除し、そのラインフェイルに割り当てるべく対応するスペアの残数を１減らし、また、ラインフェイルと判定された行や列のアドレスを記憶する。
【０１７２】
ステップＳ２０２は、新たにラインフェイルが検出されなくなるまで繰り返し行う。
【０１７３】
ここで、ステップＳ２０１は、不良ビットデータを逐次読み込む過程において、同じ行アドレスあるいは同じ列アドレスが連続して出現する場合にのみ、ラインフェイルの検出を行うものであった。そして、ラインフェイルが検出される度にそれに割り当てるべく対応するスペアの残数が減少していく。従って、ステップＳ１０１，Ｓ２０１のサイクルが終了した後で、再度、ラインフェイルが検出できるケースがあり得る。
【０１７４】
図１７の例では、これにステップＳ１０１，Ｓ１０２を適用後、入力データ格納用ファイルに書き込まれた２２個の不良ビットのアドレスのデータに対してステップＳ２０２を適用すると、列アドレス１７の列がラインフェイルとして検出される。なぜなら、列アドレス１７を持つ不良ビットデータは４つあり、そのうち３つは行列Ｂの上行に属する。ところが、上水平スペアの残数は図１８（ｂ）のように２本なので（行アドレス１０のラインフェイルの救済に使用したので）、これら３つの不良ビットは右垂直スペアで救済せざるを得ないからである。
【０１７５】
そこで、列アドレス１７に属する４つの不良ビットを入力データ格納用ファイルから全て削除する。この時点での入力データ格納用ファイルの内容の一例を図２１に示す。図２１のように未救済の不良ビット数は計１８個に縮小される。
【０１７６】
また、右垂直スペアの残数を１減らして２とする。この時点で、図１７の具体例に対するスペアの残数は、図１８（ｄ）に示すように、上水平スペアが２本、下水平スペアが３本、左垂直スペアが３本、右垂直スペアが２本となる。また、図１８（ｅ）に示すように、列アドレス１７を記憶する。なお、仮想の右垂直スペアにより救済される行列Ｂにおける列アドレス１７のラインを図２０中に「ラインフェイル（その２）」として示す。
【０１７７】
なお、図２１では後の処理のために各エントリに不良ビットの属するサブブロックの番号（ＢＫＬｉにおけるｉの値）を登録してあるが、登録せずに必要時に求めるようにしても良い。
【０１７８】
本処理において、スペアが不足し、ラインフェイルが救済できない場合は、当該ＲＡＭを救済できないので、ステップＳ７０２に進む。
【０１７９】
ここで、後の処理のためにステップＳ２０１とＳ２０２のラインフェイルの救済がすべて完了したときの上水平スペアの残数をｒｅｓ ｕ、下水平スペアの残数をｒｅｓ ｄ、左垂直スペアの残数をｒｅｓ ｌ、右垂直スペアの残数をｒｅｓ ｒと記述する。
図１７の具体例の場合、
ｒｅｓ ｕ＝２
ｒｅｓ ｄ＝３
ｒｅｓ ｌ＝３
ｒｅｓ ｒ＝２
となる。
【０１８０】
（４）次に、ステップＳ３０１の２部グラフ作成部３０による２部グラフの作成処理について説明する。
【０１８１】
ステップＳ３０１では、入力データ格納用ファイルに書き込まれているアドレスのデータをもとに、２部グラフデータを作成する。
【０１８２】
行列Ｂの各成分は正常ビットまたは不良ビットの何れかであるため、２部グラフＧ＝（Ｖ１  ，Ｖ２  ，Ｅ）で等価に実現できる。実際、行列Ｂの行の添字集合、列の添字集合がそれぞれＧの左頂点集合Ｖ１  、右頂点集合Ｖ２  に対応し、行列Ｂの不良ビットセルがＧの辺（Ｅの要素）に対応する。ここで、行列ＢはステップＳ１０１，Ｓ２０１，Ｓ２０２を経て、ラインフェイルが検出された場合には、実質的に縮小されたものとなっている。
【０１８３】
例えば、本具体例について、ステップＳ１０１，Ｓ２０１，Ｓ２０２を経た後の入力データ格納用ファイルに書き込まれているアドレスのデータをもとに、縮小された行列Ｂを示すと、図２２のようになる。この図２２の行列Ｂに対応する２部グラフを図２３に示す。
【０１８４】
なお、実際のプログラムの中（計算機内部）では、この行列ＢのデータをＢ（ｉ，ｊ）のような２次元配列等によりそのままの形で持つ必要はなく、直接２部グラフのデータに落とせば良い。
【０１８５】
本例では、図２３のように最初から２部グラフとして保持していることになる。この場合、本処理では、図２４（ａ）に示すように各行アドレスに対するリンク先の列アドレスおよび図２４（ｂ）に示すように各列アドレスに対するリンク先の行アドレスのテーブルを作成することになる。また、計算機内部の処理として、行アドレスおよび列アドレスに１から順に排他的に番号を付け替える場合、番号により行か列かが識別できるため図２４（ａ）と（ｂ）は１つのテーブルで実現可能である。さらに、図２４（ａ）と（ｂ）は図２１と合体させて設けても良い。
【０１８６】
なお、ステップＳ２０２が終了した時点でビットマップの形で不良データのアドレス情報を保持する場合には、本処理では、図２１と図２４のテーブルを作成することになる。
【０１８７】
（５）次に、ステップＳ４０１の最大マッチング作成部４０による最大マッチングの作成処理について説明する。
【０１８８】
ステップＳ４０１では、ステップＳ３０１で作成した２部グラフに対して、その最大マッチングを算出する。２部グラフＧの辺集合Ｅの部分集合Ｘにおいて、Ｘに含まれるどの２辺も端点を共有しないとき、Ｘを「最大マッチング」と言う。２部グラフの最大マッチングを求めるには例えばＨｏｐｃｒｏｆｔ  ＆  Ｋａｒｐのアルゴリズムを用いることができる。このアルゴリズムは、例えば文献「情報の構造」浅野孝夫著、日本評論社に詳しく開示されている。求めた最大マッチングは、本処理で救済不可の判定に使用され、また後のステップＳ５０１でＤＭ分解の作成に使用される。
【０１８９】
さて、２部グラフＧ＝（Ｖ１  ，Ｖ２  ，Ｅ）の頂点の部分集合Ｕ１  ，Ｕ２  （Ｕ１  はＶ１  の部分集合、Ｕ２  はＶ２  の部分集合）対して、
［ｕ，ｖ］が２部グラフＧの辺ならば、
「ｕはＵ１  の要素である」または「ｖはＵ２  の要素である」、
が成立するとき、式（２）で表される集合を２部グラフＧの被覆という。頂点数が最小の被覆を「最小被覆」と言う。最小被覆は、スペアの本数に制限がないとした場合の最適な救済解に相当するものである（したがって、ここでの最小被覆により得られた救済解では実現可能の場合と実現不可能の場合とがある）。
【０１９０】
【数２】
0003581249.tif 000003
【０１９１】
本処理では、「最大マッチングに含まれる辺の数は最小被覆に含まれる頂点の数に等しい」というＫｏｎｉｇ−Ｅｇｅｒｖａｒｙの定理（例えば上記文献「情報の構造」に開示されている）に従い、最大マッチングに含まれる辺の数がスペアの残数の総和よりも大きい場合は、当該ＲＡＭの救済解は存在し得ないので、ステップＳ７０１に進む。
【０１９２】
図２３の２部グラフに対する最大マッチングの一例と最小被覆の一例を図２５に示す。図２５において、太線で示した辺の集合が１つの最大マッチングであり、黒く塗り潰した頂点の集合が１つの最小被覆である。最大マッチングは例えば図２６のようにあるいは図２４に最大マッチングを示すフラグを設けることなどにより記憶される。
【０１９３】
この場合、最大マッチングに含まれる辺の数は９で、スペアの残数の総和１０（図１８（ｄ）に示すように、上水平スペアが２本、下水平スペアが３本、左垂直スペアが３本、右垂直スペアが２本）よりも小さいので、救済不可とは判定されないので、ステップＳ７０１には進まず、次のステップＳ５０１に進む。
【０１９４】
（６）次に、ステップＳ５０１のＤＭ分解作成部５０によるＤＭ分解の作成処理について説明する。
【０１９５】
ステップＳ５０１では、ステップＳ４０１で求めた最大マッチングをもとに、２部グラフＧのＤＭ分解を求める。行列のＤＭ分解は、ブロック三角化（階層的分解）の最も細かい分解として知られている（例えば文献「線形計算」、岩波講座  応用数学［方法２］、森ほか著に開示されている）。ＤＭ分解は、直感的に述べれば、与えられた行列を幾つかの部分行列が対角線上に並び、しかもその対角線部分の左下半の成分が全て０になるように、行と列を並べ変えたものである（ＤＭ（Ａ．Ｌ，Ｄｕｌｍａｇｅ  ＆  Ｎ．Ｓ．Ｍｅｎｄｅｌｓｏｈｎ）分解の厳密な定義については上記文献「情報の構造」等に詳しい）。ＤＭ分解は、ステップＳ４０１で求めた最大マッチングのデータをもとに、強連結成分分解のアルゴリズム（例えば上記文献「情報の構造」に開示されている）を用いることによって高速に求まる。求められたＤＭ分解は、ラインフェイル処理の後に残った不良ビットを３種類の不良ビットに分類し、各分類毎に順次Ｂスペアを割り当てていく処理に利用される。
【０１９６】
図２７（ａ）に並べ変える前の行列の一例を、図２７（ｂ）に並べ変えた後の行列のＤＭ分解の一例を示す（なお図２７は一般的な説明のための図であり図１６の例に対応するものではない）。図２７において、行列の左側の数字は行番号を、上側の数字は列番号を表す。各部分行列には通常左上部から順に、Ｇ１  ，Ｇ２  ，Ｇ３  ，…，Ｇｎ  ，Ｇ０  という名前を付ける。ここで、Ｇ１  とＧ０  は、特別な部分行列であり、行列によっては存在しない場合もある。Ｇ２  ，Ｇ３  ，…，Ｇｎ  は、常に正方行列であり、２部グラフとして見た場合には完全マッチングを含むような部分行列である。
【０１９７】
ＤＢ分解においては、対角線部分の右上半の成分には１が含まれていてもよい。それらの１は部分行列間の隣接関係を表している。その隣接関係をグラフで表現したものが図２７（ｃ）に示す有向グラフである。本実施形態では、この有向グラフをＤＭ分解の縮約グラフと呼び、ＧＤＭという記号で表す。
【０１９８】
図２５の最大マッチングをもとに、図２３の２部グラフのＤＭ分解を求めると、図２８のＤＭ分解が得られる。このＤＭ分解の縮約グラフＧＤＭを図２９に示す。
【０１９９】
なお、計算機内部では、例えば、ＤＭ分解とその縮約グラフＧＤＭは図３０のように保持することができる。
【０２００】
（７）次に、ステップＳ５５１の救済解作成部６０による孤立不良のグループ分け処理について説明する。
【０２０１】
ステップＳ５５１では、ＤＭ分解のデータをもとに、孤立不良をメモリーブロックの構造に応じたいくつかのグループに分類する。
【０２０２】
例えば、図１のような構造の場合には、孤立不良を４つのグループに分類する。なお、スペアのサブブロックへの適用制限がない場合には、グループは１つになる。
【０２０３】
ＤＭ分解行列において１×１の分解成分（部分行列）を形成し、かつＤＭ分解グラフＧＤＭにおいてＧ０  ，Ｇ１  以外のどの頂点とも隣接していない成分を孤立不良と呼ぶことにする。通常、ある不良ビットに対して、その不良ビットを含む行および列に、他の不良ビットが全く存在しない場合に、その不良ビットを孤立不良と呼ぶが、本実施形態では、原則としてＧ０  には垂直スペアを、Ｇ１  には水平スペアを割当てるため、前記のようなより広い意味で孤立不良という語句を用いる。
【０２０４】
図１のような構造の場合、孤立不良は、それがＢＬＫ１，ＢＬＫ２，ＢＬＫ３，ＢＬＫ４のいずれに属するかによって、４つのグループに分類することができる。ＢＬＫ１に属する孤立不良のグループをＩ１で表す。同様に、ＢＬＫ２，ＢＬＫ３，ＢＬＫ４のそれぞれに属する孤立不良のグループをＩ２，Ｉ３，Ｉ４で表す。
【０２０５】
これら各グループごとに、水平スペアの割り当て可能な上限本数を設定し、（ｓｕｐ Ｉ１，ｓｕｐ Ｉ２，ｓｕｐ Ｉ３，ｓｕｐ Ｉ４）で表す。ステップＳ２０１，Ｓ２０２が行われた後の上水平スペアの残数をｒｅｓ ｕとおき、下水平スペアの残数をｒｅｓ ｄとおくと、ｓｕｐ Ｉ１はＩ１の要素数およびｒｅｓ ｕの値の小さい方の値、ｓｕｐ Ｉ２はＩ２の要素数とｒｅｓ ｄの値の小さい方の値としてそれぞれ設定することができる。同様に、ｓｕｐ Ｉ３はＩ３の要素数とｒｅｓ ｕの値の小さい方の値、ｓｕｐ Ｉ４はＩ４の要素数とｒｅｓ ｄの値の小さい方の値としてそれぞれ設定することができる。
【０２０６】
図２８の例では、行ラベル１４、列ラベル１４の不良ビット（Ｇ５  に対応）、および行ラベル２９、列ラベル２２の不良ビット（Ｇ６  に対応）が共に孤立不良である。前者はＩ１に属し、後者はＩ４に属する。この例には他の孤立不良はないので、Ｉ２とＩ３は空集合である。ステップＳ２０１，Ｓ２０２が行われた後において、ｒｅｓ ｕ＝２、ｒｅｓ ｄ＝３、ｒｅｓ ｌ＝３、ｒｅｓ ｒ＝２であるので、ｓｕｐ Ｉ１＝１、ｓｕｐ Ｉ２＝ｓｕｐ Ｉ３＝０、ｓｕｐ Ｉ４＝１である。
【０２０７】
なお、後述する処理ループにおいて次のステップＳ６０１まで後戻りする場合には、ステップＳ６０１の処理に入る直前に各種データの内容を再現できるように保存しておく。
【０２０８】
ところで、一般に実際のＲＡＭデータの場合、不良ビットは、ある特定の行あるいは列に連続して発生するか、あるいはどの行、列にも一様に（ランダムに）発生するというケースが多い。ある特定の行あるいは列に不良ビットが連続して発生する場合、そのような行あるいは列はラインフェイルとしてステップＳ２０１およびＳ２０２において救済される（スペアが割り当てられる）。従って、ステップＳ３０１以降では、どの行、列にも一様に発生する不良ビットを扱うことになる。不良ビットがどの行、列にも一様に発生する場合、不良ビットの多くは孤立不良となる場合が多い。
【０２０９】
（８）次に、ステップＳ６０１の救済解作成部６０よるＧ１  ，Ｇ０  へのスペアの割り当て処理について説明する。
【０２１０】
ステップＳ６０１では、ＤＭ分解の分解成分Ｇ０  ，Ｇ１  （ただしそれが存在する場合）に水平スペアまたは垂直スペアを割り当てる。
【０２１１】
まず、Ｇ１  の行ラベルに対応する行列Ｂの全てのラインに水平スペアを割り当てる。もしＧ１  の行ラベルに対応する行列Ｂの全てのラインへの水平スペアの割り当てが、水平スペアの残数の不足により不可能な場合は、Ｇ１  の行ラベルに対応する行列Ｂのラインのうち、ＤＭ分解行列においてＧ１  の右側に１（不良ビット）があるようなラインについては水平スペアを割り当て、他のラインについては、使用可能なスペア数の範囲内で水平または垂直スペアを割り当てる。
【０２１２】
次に、Ｇ０  の列ラベルに対応するＢの全てのラインに垂直スペアを割り当てる。もしＧ０  の列ラベルに対応するＢの全てのラインへの垂直スペアの割り当てが、垂直スペアの残数の不足により不可能な場合は、Ｇ０  の列ラベルに対応するＢのラインのうち、ＤＭ分解行列においてＧ０  の上側に１（不良ビット）があるようなラインについては垂直スペアを割り当て、他のラインについては、使用可能なスペア数の範囲内で垂直または水平スペアを割り当てる。
【０２１３】
Ｇ１  ，Ｇ０  へのスペアの割り当てによってスペアの残数が変更されるが、その変更後の上水平スペア、下水平スペア、左垂直スペア、右垂直スペアの残数を、改めてそれぞれｒｅｓ ｕ、ｒｅｓ ｄ、ｒｅｓ ｌ、ｒｅｓ ｒとおく。また、その行または列のラインを記憶する。
【０２１４】
もしスペアの残数が足りず、Ｇ０  ，Ｇ１  へのスペアの割り当てが求まらない場合（どのようにしてもＧ０  ，Ｇ１  が救済できない場合）は、スペア不足として、ステップＳ７０２に移る。
【０２１５】
図２８の例では、行ラベル１の行に上水平スペアが、行ラベル２５の行に下水平スペアが、列ラベル２７の列に右垂直スペアがそれぞれ割り当てられる。従って、スペアの残数は、図１８（ｆ）に示すように、ｒｅｓ ｕ＝１、ｒｅｓ ｄ＝２、ｒｅｓ ｌ＝３、ｒｅｓ ｒ＝１となる。また、図１８（ｇ）に示すように、行ラベル１、行ラベル２５、列ラベル２７を記憶する。なお、図２８のＤＭ分解おける本処理でのスペアの割り当て結果を図３１（ａ）に示す。また、仮想の上水平スペアにより救済される行列Ｂにおける行ラベル１、行ラベル２５、列ラベル２７のラインをそれぞれ図２０中にＧ１  （１）、Ｇ１  （２）、Ｇ０  として示す。
【０２１６】
ここで、後述する処理ループにおいて次のステップＳ６０２まで後戻りする場合のために、ステップＳ６０２の処理に入る直前の各種データの内容を保存しておくものとする。
【０２１７】
（９）次に、ステップＳ６０２の救済解作成部６０による孤立不良グループへのスペア割り当て処理について説明する。図３２にＳ６０２およびＳ６０３の処理手順の一例を示す。
【０２１８】
ステップＳ６０２では、孤立不良が存在する場合に、各孤立不良グループＩ１，Ｉ２，Ｉ３，Ｉ４のそれぞれにスペアを割り当てる。孤立不良グループＩ１，Ｉ２，Ｉ３，Ｉ４の要素数をそれぞれ｜Ｉ１｜，｜Ｉ２｜，｜Ｉ３｜，｜Ｉ４｜で表すものとする。
【０２１９】
孤立不良の各グループＩ１，Ｉ２，Ｉ３，Ｉ４への水平スペアの割り当て本数の組合せ（ａ，ｂ，ｃ，ｄ）を１つ選ぶ。
【０２２０】
ａは０〜上限数ｓｕｐ Ｉ１の範囲の値、
ｂは０〜上限数ｓｕｐ Ｉ２の範囲の値、
ｃは０〜上限数ｓｕｐ Ｉ３の範囲の値、
ｄは０〜上限数ｓｕｐ Ｉ４の範囲の値
をそれぞれ取り得るので、このような組合せは、計（ｓｕｐ Ｉ１＋１）×（ｓｕｐ Ｉ２＋１）×（ｓｕｐ Ｉ３＋１）×（ｓｕｐ Ｉ４＋１）通りある。
【０２２１】
なお、組合せ（ａ，ｂ，ｃ，ｄ）の選択方法としては種々のものが考えられる。垂直スペア優先の場合は、まず、ａ＝ｂ＝ｃ＝ｄ＝０とし、以降、ａを０からｓｕｐ Ｉ１まで１ずつ増加していき、次に、ｂ＝１として、ａを０からｓｕｐ Ｉ１まで１ずつ増加していく、といったようにａ、ｂ、ｃ、ｄの順に４重のループを形成するような形で選択していく方法が好ましい。水平スペア優先の場合は、まず、ａ＝ｓｕｐ Ｉ１、ｂ＝ｓｕｐ Ｉ２、ｃ＝ｓｕｐ Ｉ３、ｄ＝ｓｕｐ Ｉ４とし、値を１ずつ減少させるようにａ、ｂ、ｃ、ｄの順に４重のループを形成するような形で選択していく方法が好ましい。その他、組合せが同一とならないようにその都度ランダムに生成していく方法など、種々のものが考えられる。
【０２２２】
次に、孤立不良の各グループＩ１，Ｉ２，Ｉ３，Ｉ４それぞれへの垂直スペアの割り当て本数の組合せを、上記水平スペアの割り当て本数の組合せ（ａ，ｂ，ｃ，ｄ）と孤立不良グループの要素数（｜Ｉ１｜，｜Ｉ２｜，｜Ｉ３｜，｜Ｉ４｜）から、（｜Ｉ１｜−ａ，｜Ｉ２｜−ｂ，｜Ｉ３｜−ｃ，｜Ｉ４｜−ｄ）と計算する。
【０２２３】
次に、上記の水平スペアの割り当て本数組合せ（ａ，ｂ，ｃ，ｄ）に対して次の４つの条件、すなわち、
ａ＋ｃ≦ｒｅｓ ｕ
ｂ＋ｄ≦ｒｅｓ ｄ
（｜Ｉ１｜−ａ）＋（｜Ｉ２｜−ｂ）≦ｒｅｓ ｌ
（｜Ｉ３｜−ｃ）＋（｜Ｉ４｜−ｄ）≦ｒｅｓ ｒ
が成り立つか否か判定する。そして、４つの条件のいずれか１つでも成り立たない場合は、上記の水平スペアの割り当て本数組合せ（ａ，ｂ，ｃ，ｄ）を選び直す。また、それに伴い、孤立不良の各グループへの垂直スペアの割り当て本数の組合せを再度計算し直す。そして、再度、上記の４つの条件について判定を行う。
【０２２４】
以上を繰り返し、４つの条件を満たす（ａ，ｂ，ｃ，ｄ）、（｜Ｉ１｜−ａ，｜Ｉ２｜−ｂ，｜Ｉ３｜−ｃ，｜Ｉ４｜−ｄ）を求める。
【０２２５】
４つの条件のすべてを満たすものが得られた場合は、スペアの割り当て本数の組合せ（ａ，ｂ，ｃ，ｄ）と（｜Ｉ１｜−ａ，｜Ｉ２｜−ｂ，｜Ｉ３｜−ｃ，｜Ｉ４｜−ｄ）を用いて、ａ＋ｃ本のラインには上水平スペアを、ｂ＋ｄ本のラインには下水平スペアを、（｜Ｉ１｜−ａ）＋（｜Ｉ２｜−ｂ）本のラインには左垂直スペアを、（｜Ｉ３｜−ｃ）＋（｜Ｉ４｜−ｄ）本のラインには右垂直スペアを割り当てる。
【０２２６】
その割り当てに伴い、スペアの残数を再計算する。その際、あるグループに２以上の孤立不良が含まれる場合に、そのグループについて使用する水平スペアの数と垂直スペアの数がいずれも０でないならば、そのグループにおいてどの孤立不良に水平スペアを使用し、どの孤立不良に垂直スペアを使用するかを決定する。この決定方法としては、例えばランダムに割り当てる方法、アドレスのソート順にまず水平スペアを割り当て次に垂直スペアを割り当てる方法など、種々の方法が考えられる。
【０２２７】
そして、各行や列のアドレスを記憶する。また、孤立不良へのスペアの割り当てによってスペアの残数が変更されるので、その変更後の上水平スペア、下水平スペア、左垂直スペア、右垂直スペアの残数を、改めてそれぞれｒｅｓ ｕ、ｒｅｓ ｄ、ｒｅｓ ｌ、ｒｅｓ ｒとおく。
【０２２８】
なお、すべての（ａ，ｂ，ｃ，ｄ）について上記処理を繰り返した結果、４つの条件のすべてを満たすものが得られなかった場合は、スペア不足としてステップＳ７０２に移る。また、上記処理の繰り返し中に時間切れとなった場合にはステップＳ７０３に移る。
【０２２９】
図２８の例の場合、ｓｕｐ Ｉ１＝１、ｓｕｐ Ｉ２＝ｓｕｐ Ｉ３＝０、ｓｕｐ Ｉ４＝１、｜Ｉ１｜＝１、｜Ｉ２｜＝｜Ｉ３｜＝０、｜Ｉ４｜＝１であり、ステップＳ６０１が行われた後のスペアの残数ｒｅｓ ｕ＝１、ｒｅｓ ｄ＝２、ｒｅｓ ｌ＝３、ｒｅｓ ｒ＝１である。
【０２３０】
ここで、例えば（ａ，ｂ，ｃ，ｄ）＝（０，０，０，１）を選んだとすると、（｜Ｉ１｜−ａ，｜Ｉ２｜−ｂ，｜Ｉ３｜−ｃ，｜Ｉ４｜−ｄ）＝（１，０，０，０）となる。
【０２３１】
そして、上記の４つの条件は、
ａ＋ｃ（＝０）≦ｒｅｓ ｕ（＝１）
ｂ＋ｄ（＝１）≦ｒｅｓ ｄ（＝２）
（｜Ｉ１｜−ａ）＋（｜Ｉ２｜−ｂ）（＝１）≦ｒｅｓ ｌ（＝３）
（｜Ｉ３｜−ｃ）＋（｜Ｉ４｜−ｄ）（＝０）≦ｒｅｓ ｒ（＝１）
とすべて満たすことがわかる。
【０２３２】
この例の場合、行ラベル２９の行に下水平スペアを、列ラベル１４の列に左垂直スペアを割り当てることになる。スペアの残数は、図１８（ｈ）に示すように、上水平スペアが１本、下水平スペアが１本、左垂直スペアが２本、右垂直スペアが１本となる。また、図１８（ｉ）に示すように、行ラベル２９と列ラベル１４を記憶する。なお、図２８のＤＭ分解における本処理でのスペアの割り当て結果を図３１（ｂ）に太線で示す。また、仮想の上水平スペアにより救済される行列Ｂにおける行ラベル２９、列ラベル１４のラインをそれぞれ図２０中にＧ６  ，Ｇ５  として示す。
【０２３３】
（１０）次に、ステップＳ６０３の救済解作成部６０による他成分へのスペアの割り当て処理について説明する。
【０２３４】
ステップＳ６０３では、Ｇ１  ，Ｇ０  および孤立不良以外のＤＭ分解の成分が存在する場合に、その各成分に対して、スペアの割り当てを行う。ＤＭ分解に含まれる分解成分のうちＧ１  ，Ｇ０  および孤立不良以外の分解成分を単に他成分と呼ぶことにする。ここでは、一般性を失うことなく、Ｇ２  ，Ｇ３  ，…，Ｇｋ  が他成分であるとして説明する。
【０２３５】
他成分Ｇ２  ，Ｇ３  ，…，Ｇｋ  については、ＤＭ分解の縮約グラフＧＤＭ上でのＧ２  ，Ｇ３  ，…，Ｇｋ  のトポロジカルソート（垂直スペア優先の場合）あるいは逆トポロジカルソート（水平スペア優先の場合）の１つから得られる最小被覆の中から、救済解を求める。
【０２３６】
なお、以下の説明においても、トポロジカルソートは垂直スペア優先の場合であり、逆トポロジカルソートは水平スペア優先の場合である。
【０２３７】
トポロジカルソートとは、アサイクリックグラフ（有向閉路を含まない有向グラフ）の点集合に対するラベル付けの１種で、どの有向辺（ｕ，ｖ）に対しても始点ｕのラベルの方が終点ｖのラベルよりも小さくなるようなラベル付けのことを指す。同様に、逆トポロジカルソートとは、アサイクリックグラフの点集合に対するラベル付けの１種で、どの有向辺（ｕ，ｖ）に対しても終点ｖのラベルの方が始点ｕのラベルよりも小さくなるようなラベル付けのことを指す。ＤＭ分解の縮約グラフＧＤＭは常にアサイクリックグラフであるため、トポロジカルソートや逆トポロジカルソートが可能である。１つのアサイクリックグラフに対して、複数のトポロジカルソートや逆トポロジカルソートが可能である。トポロジカルソートや逆トポロジカルソートの１つは深さ優先探索（例えば上記文献「情報の構造」に開示されている）によって求めることができる。
【０２３８】
垂直スペア優先の場合、Ｇ２  ，Ｇ３  ，…，Ｇｋ  の最小被覆は、まず、Ｇ２  ，Ｇ３  ，…，Ｇｋ  に対するトポロジカルソートの１つを求め、次にそのトポロジカルオーダーに逆らわないように水平または垂直スペアを割り当てることによって求めることができる。ここで、「トポロジカルソートオーダーに逆らわないように」とは、あるＧｊ  （ｊ＞１）に対して水平スペアを割当てたならば、Ｇｊ  のトポロジカルソートのラベルよりも小さなラベルを持つ成分Ｇｊ  （１＜ｉ＜ｊ）に対しても水平スペアを割当てなければならないという意味である。
【０２３９】
同様に、水平スペア優先の場合、Ｇ２  ，Ｇ３  ，…，Ｇｋ  の最小被覆は、まず、Ｇ２  ，Ｇ３  ，…，Ｇｋ  に対する逆トポロジカルソートの１つを求め、次にその逆トポロジカルオーダーに逆らわないように水平または垂直スペアを割り当てることによって求めることができる。ここで、「逆トポロジカルソートオーダーに逆らわないように」とは、あるＧｊ  （ｊ＞１）に対して垂直スペアを割当てたならば、Ｇｊ  の逆トポロジカルソートのラベルよりも小さなラベルを持つ成分Ｇｊ  （１＜ｉ＜ｊ）に対しても垂直スペアを割当てなければならないという意味である。
【０２４０】
上記の制約はＤＭ分解のどの成分にも含まれない不良ビットの救済方法を規定するものである。
【０２４１】
１つのトポロジカルソートや逆トポロジカルソートからは逐次複数の最小被覆を構成することができる（例えば上記文献「情報の構造」に開示されている）。従って、それらの最小被覆を１つずつ生成し、スペアの残数制限と比較することによってスペアの残数制限を満たす最小被覆を求めればよい。
【０２４２】
もし、スペアの残数制限を満たす最小被覆が求まらなかった場合は、ステップＳ６０２に戻り、孤立不良の各グループへの水平スペアの割り当て本数の組合せ（ａ，ｂ，ｃ，ｄ）を選び直し、孤立不良へのスペアの割り当てを決め、再度、Ｇ２  ，Ｇ３  ，…，Ｇｋ  に対する最小被覆を探索する。
【０２４３】
図２８の場合、Ｇ２  ，Ｇ３  ，Ｇ４  が他成分である。Ｇ２  ，Ｇ３  ，Ｇ４  をトポロジカルソートすると、Ｇ２  ，Ｇ３  ，Ｇ４  となる。Ｇ２  ，Ｇ３  ，Ｇ４  を逆トポロジカルソートすると、Ｇ４  ，Ｇ３  ，Ｇ２  となる。このオーダー（順序）に従って、例えば、Ｇ２  に水平スペアを、Ｇ３  ，Ｇ４  に垂直スペアを割り当てることができる。すなわち、行ラベル４の行に上水平スペアを、行ラベル２７の行に下水平スペアを、列ラベル６の列に左垂直スペア、列ラベル１０の列に左垂直スペアを割り当てることになる。
【０２４４】
このときスペアの残数は、図１８（ｊ）に示すように、上水平スペアが０本、下水平スペアが０本、左垂直スペアが０本、右垂直スペアが１本となる。また、図１８（ｋ）に示すように、これら行ラベル４、行ラベル２７、列ラベル６、列ラベル１０を記憶する。なお、図２８のＤＭ分解における本処理でのスペアの割り当て結果を図３１（ｃ）に太線で示す。また、仮想の上水平スペアにより救済される行列Ｂにおける行ラベル４、行ラベル２７、列ラベル６、列ラベル１０のラインをそれぞれ図２０中にＧ２  （１），Ｇ２  （２），Ｇ３  ，Ｇ４  として示す。
【０２４５】
以上のようにしてスペアの残数内で他成分へのスペアの割り当てができたので、これで行列Ｂの救済解が１つ求まったことになる。
【０２４６】
なお、ステップＳ６０２，Ｓ６０３の繰り返し操作を行っても、他成分に対する最小被覆が見つからなかった場合は、スペア不足としてステップＳ７０２に移る。また、上記の一連の手続きで、もし制限時間をオーバーした場合は、時間不足としてステップＳ７０３に移る（上記の一連の手続きは非常に高速に行われるため、救済のための制限時間をオーバーすることは非常にまれであると考えられる）。
【０２４７】
なお、上記処理において、解が得られずステップＳ６０２に戻る前に、いくつかのトポロジカルソートあるいは逆トポロジカルソートについて同様の処理を繰り返し、それでも解が得られなかった場合にステップＳ６０２に戻るようにしても良い。また、孤立不良がない場合にのみ、このようなトポロジカルソートや逆トポロジカルソートのループ処理を行うようにしても良い。
【０２４８】
（１１）次に、ステップＳ７０１の救済結果出力部７０による救済の対応データを作成し出力（あるいは送信）する処理について説明する。
【０２４９】
ステップＳ７０１では、ステップＳ６０１〜Ｓ６０３の過程で得られた救済解（行列Ｂの不良ラインとＢのスペアの間の対応関係）をもとに、本来のメモリーブロック（行列Ａ）の不良ラインと本来のスペアの間の対応関係を求める。
【０２５０】
行列Ｂの救済解において、ＢのスペアがＡのスペアを救済している（に対応している）場合は、そのＡスペアはＡの不良ラインの救済には使用しない。ＢのスペアがＡの不良ラインを救済している場合は、使用しないことが決まったＡスペア以外のＡスペアを割り当てる。この割り当て方法は、前述した定理の証明の中に述べたように任意である。
【０２５１】
以上の方法で定めた救済の対応データを出力する。
【０２５２】
図１６の例の場合、図２０に示されるように、行ラベル１０の行と、列ラベル１７の列がラインフェイルとして検出され、行ラベル１，４，２５，２７，２９の行と、列ラベル６，１０，１４，２７の列がステップＳ６０１からＳ６０３の過程で、救済されるべき不良ラインとして検出される。つまり、行列Ｂの救済解は、これらの行、列へのＢのスペア（仮想スペア）の割り当てである。この救済解をもとに、行列Ａの不良ラインとＡのスペアの間の対応関係を求める。
【０２５３】
この場合、行列Ａについて、行ラベル１０，２５の行と、列ラベル１４，１７，２７の列が救済されるラインとなる。また、行ラベル１，２９が救済に使用できないスペアとなり、行ラベル２，３，２８，２９の行と、列ラベル１〜３，２８〜２９の列のうちから救済に使用するスペアが割り当てられることになる。
【０２５４】
対応関係の具体例は次のようになる。まず、行ラベル１，２９の行は共にＡスペアであるので、行ラベル１，２９の行はどちらもＡの不良ラインの救済には使用しない。次に行ラベル４，１０のＡの不良ラインにそれぞれＡの上水平スペア２，３を割り当て、行ラベル２５，２７のＡの不良ラインにそれぞれ、下水平スペア２８，３０を割り当てる。最後に列ラベル６，１０，１４のＡの不良ラインにそれぞれＡの左垂直スペア１，２，３を割り当て、列ラベル１７，２７のＡの不良ラインにそれぞれＡの右垂直スペア２８，２９を割り当てる。
【０２５５】
なお、前述したように広い意味での救済解を出力するようにしてもよい。
【０２５６】
（１２）次に、ステップＳ７０２の救済結果出力部７０による救済不可を出力（あるいは送信）する処理について説明する。
【０２５７】
ステップＳ７０２では、スペア数が不足した場合は救済不可として、その旨を示すメッセージを出力する。
【０２５８】
（１３）次に、ステップＳ７０３の救済結果出力部７０による時間内の救済不可を出力（あるいは送信）する処理について説明する。
【０２５９】
ステップＳ７０３では、救済のための制限時間をオーバーした場合は、時間内の救済不可として、その旨を示すメッセージを出力する。
【０２６０】
以上述べた実施形態は本発明を実施するための例であり、種々の変形が可能である。
【０２６１】
例えば、ラインフェイルの算出はハード上の処理あるいはメモリーテスト装置側の処理とし、ステップＳ１０１で入力データとして入力されるデータは、予め算出されたラインフェイルのアドレスデータと、ラインフェイルを全て算出した後の不良ビットの情報であるとしてもよい。その場合、ステップＳ２０１，Ｓ２０２は省略できる。
【０２６２】
また、ステップＳ２０２の後で、ＢＬＫ１，ＢＬＫ２，ＢＬＫ３，ＢＬＫ４の各々に対して、その中に含まれる不良ビットの、互いに異なる行アドレスの総数、および互いに異なる列アドレスの総数をカウントし、もしその行アドレスの総数および列アドレスの総数が共にあるしきい値を越えたならば、スペア不足としてステップＳ７０２に進んでもよい。ここで、しきい値というのは、Ａスペアの数によって決定される。すなわち、Ａの上水平スペア数をｎ、左垂直スペア数をｍとするとき、ＢＬＫ１の行アドレスの総数に対するしきい値はｎ＋ｍ×ｎ、列アドレスの総数に対するしきい値はｍ＋ｎ×ｍで表される。つまり、これらのしきい値はＡの上水平スペアおよび左垂直スペアを全て使えばＢＬＫ１が救済可能となる、ＢＬＫ１の最大サイズに対応している。
【０２６３】
また、ステップＳ１０１とＳ２０１の処理は、前述したようにこれらを交互に繰り返し行うのではなく、各々をバッチ処理的に実行することも可能である。さらに、バッチ処理的に実行する場合には、Ｓ１０１の終了後、Ｓ２０１を省いて次のＳ２０２を行ってもよい。また、ラインフェイル処理として、他のアルゴリズムを用いることも可能である。例えば、“Ｅｆｆｉｃｉｅｎｔ  ｓｐａｒｅ  ａｌｌｏｃａｔｉｏｎ  ｆｏｒ  ｒｅｃｏｎｆｉｇｕｒａｂｌｅ  ａｒｒａｙｓ”，ｂｙ  Ｓｙ−Ｙｅｎ  Ｋｕｏ  ａｎｄ  Ｗ．Ｋｅｎｔ  Ｆｕｃｈｓ，ＩＥＥＥ  Ｄｅｓｉｇｎ  ａｎｄ  Ｔｅｓｔ，ｐｐ．２４−３１，１９８７（より詳しくはそのＦｉｇ．５）に開示されたものを用いることも可能である。
【０２６４】
また、ステップＳ４０１の最大マッチングの辺数による「救済解なし」の判定は、行列Ｂの上部、下部、左部、右部、およびこれらの共有部分（左上部、右上部、左下部、右下部）のそれぞれに限定して行うことも可能である。例えば２部グラフＧの部分グラフで、行列Ｂの上部の行、列に対応する頂点およびそれらの頂点間の辺集合だけからなる部分グラフに対して、最大マッチングを求め、その辺数と行列Ｂの上部で使用可能なスペアの総数とを比較し、もし前者が後者よりも大きければ「救済解なし」と判定し、ステップＳ７０２に進むことも可能である。
【０２６５】
この判定の範囲は、種々の組合せで行う場合が考えられ、例えば、前述したメモリーブロック全部を対象範囲とする他に、（１）上部、下部、左部および右部のそれぞれについて判定を行う方法、（２）左上部、右上部、左下部および右下部のそれぞれについて判定を行う方法、メモリーブロック全部と（１）の組合せ、メモリーブロック全部と（２）の組合せ、メモリーブロック全部と（１）と（２）の組合せなどが考えられる。複数の判定を行う場合には、いずれか１つの判定で「救済解なし」と判定されれば、当該ＲＡＭは救済不可となるので、その判定が出された時点でステップＳ７０２に進む。
【０２６６】
また、ステップＳ５５１の後で、孤立不良グループＩ１，Ｉ２，Ｉ３，Ｉ４の内部から、行列Ａの本来のスペア（Ａスペア）に属するような孤立不良を抜き出しておき、ステップＳ６０２においては、まず、そのような孤立不良を、Ａ内を横切らないようにＢスペアで救済することも可能である。つまり、孤立不良を含むＡスペアは、Ａ内の不良ビットの救済には使用しないとしてしまうことも可能である。これによって、最終的なスペアの使用総数を減らせる場合がある。
【０２６７】
また、ステップＳ６０２とステップＳ６０３の順番を入れ替えることも可能である。つまり、他成分へのスペアの割り当てを行ってから、その時点のスペアの残数を用いて孤立不良グループへのスペアの割り当てを行うことも可能である。
【０２６８】
また、ステップＳ６０３において、Ｇ２  ，Ｇ３  ，…，Ｇｋ  の最小被覆を求める方法は、トポロジカルソートや逆トポロジカルソートの１つから得られる最小被覆だけに限定しているが、文献“Ｇｅｎｅｒａｔｉｏｎ  ｌｉｎｅａｒ  ｅｘｔｅｎｓｉｏｎｓ  ｆａｓｔ”，ｂｙ  Ｇ．Ｐｒｕｅｓｓｅ  ａｎｄ  Ｆ．Ｒｕｓｋｅｙ，ＳＩＡＭ  Ｊ．Ｃｏｍｐｕｔｉｎｇ，Ｖｏｌ．２３，ｐｐ．３７３−３８６，１９９４の方法を用いて、トポロジカルソートあるいは逆トポロジカルソートを全て求めて、他の最小被覆をチェックすることも可能である（ただし、この場合、異なるトポロジカルソートや逆トポロジカルソートから同一の最小被覆が得られることが多々あり得ることに注意する）。あるいは文献“Ｇｅｎｅｒａｔｉｏｎ  ｏｆ  ｍａｘｉｍｕｍ  ｉｎｄｅｐｅｎｄｅｎｔ  ｓｅｔｓ  ｏｆ  ａ  ｂｉｐａｒｔｉｔｅ  ｇｒａｐｈ  ａｎｄ  ｍａｘｉｍｕｍ  ｃｌｉｑｕｅｓ  ｏｆ  ａ  ｃｉｒｃｕｌａｒ−ａｒｃ  ｇｒａｐｈ”，ｂｙ  Ｔ．Ｋａｓｈｉｗａｂａｒａ，ｅｔ  ａｌ，Ｊ．Ａｌｇｏｒｉｔｈｍｓ，Ｖｏｌ．１３，ｐｐ．１６１−１７４，１９９２の方法を用いて最小被覆を全て列挙することも可能である。
【０２６９】
また、ステップＳ６０３において、分解成分Ｇ２  ，Ｇ３  ，…，Ｇｋ  の中にサイズの大きな分解成分がある場合は、その分解成分を水平スペアと垂直スペアが混在したスペアの集まりで救済してから、残りの成分の最小被覆を求めることも可能である。
【０２７０】
また、ステップＳ６０２，Ｓ６０３の繰り返し操作を行っても、他成分に対する最小被覆が見つからなかった場合は、ステップＳ６０１に戻り、分解成分Ｇ１  ，Ｇ０  へのスペアの割り当て方法を変更してもよい。その場合、Ｇ１  ，Ｇ０  は、水平スペアと垂直スペアの混在したスペアの集まりで割り当てを行うことになる。ステップＳ６０１では、Ｇ１  の右側に１があるようなラインについては水平スペアを割り当て、Ｇ０  の上側に１があるようなラインについては垂直スペアを割り当てるとしたが、孤立不良の定義を本来の狭義で解釈することによって、Ｇ１  の右側に１を含むラインに垂直スペアを割り当てたり、Ｇ０  の上側の１を含むラインに水平スペアを割り当てることも可能である。なお、この場合、例えば、ラインフェイル検出の終了直後の各種データの内容を保存しておき、割り当て方法を変更するときは各種データの内容を保存時の状態に戻すようにする。
【０２７１】
ここで、Ｇ１  の行ラベル、列ラベルに対応する行、列に対して、水平スペアと垂直スペアの混在したスペアの集まりで割り当てを行う必要のある例を図３３に示す。図３３は、入力時における行列Ｂから、その零行と零列を削除して書いたものである。この例には、上水平、下水平スペアがそれぞれ４本、左垂直、右垂直スペアがそれぞれ８本ずつあるものとする。なお、図３３では、行や列のアドレスを付け替えている。
【０２７２】
図３４は、図３３においてラインフェイル（列ラベル５の列）を算出した後の行列Ｂに対するＤＭ分解行列である。そして、図３３において○印または×印をつけた行ラベルおよび列ラベルの行、列がＢの救済解である。そのうち○印のついた行ラベルおよび列ラベルの行、列は、救済すべきＡの不良ラインを示し、×印のついた行ラベルおよび列ラベルの行、列は、Ａの不良ラインの救済には使用しないとした、Ａスペアを示している。
【０２７３】
本実施形態に係る救済処理方法では、不良ビットを含むスペア（不良スペア）を特別扱いせずに、メイン領域のラインと同等に扱っている。そのため、不良スペアを使わなくても救済できるような解があっても、そのような解を出力するとは限らない。その場合、救済解における使用スペア数の最小化という面からは不利である。そこで、次のような改良も可能である。
【０２７４】
まず、不良ビットのあるスペアは全てラインフェイルとみなして解いてみる。つまり、ステップＳ２０２に続くステップＳ２０３として「不良スペアは全てラインフェイルとみなす」という処理を追加する。そして、ステップＳ４０１、Ｓ６０１、Ｓ６０２、あるいはＳ６０３から、ステップＳ７０２に進んだ場合は、救済不可の送信の代わりにステップＳ３０１に戻る処理を追加する（ただし、ここで戻るという処理は１回限りとする）。ステップＳ３０１に戻った場合は、不良スペアのデータをラインフェイルのデータから外し、該不良スペア上の不良ビットデータを追加した不良ビットデータの集まりを救済の対象にする。
【０２７５】
次に、本発明のより詳しい第２の実施形態に係る半導体不良ビット救済処理装置について説明する。
【０２７６】
図３５は、本実施形態に係る半導体不良ビット救済処理装置の概略構成を示すブロック図である。この半導体不良ビット救済処理装置は、データ入力部１０、ラインフェイル判定部２０、線形計画問題表現部３５、２段階単体法適用部４５、救済結果出力部７０を備えている。
【０２７７】
データ入力部１０、ラインフェイル判定部２０、救済結果出力部７０については第１の実施形態と同様である。
【０２７８】
線形計画問題表現部３５は、ラインフェイル判定部２０を経て縮小された不良ビットデータ、およびスペアの適用範囲と本数制限を線形計画問題で表現する。
【０２７９】
２段階単体法適用部４５は、上記線形計画問題に２段階単体法を適用し、不良ラインとスペアの間の対応関係を決める。
【０２８０】
次に、本実施形態に係る半導体不良ビット救済処理装置の処理手順を図３６のフローチャートを用いて説明する。ただし、ステップＴ１０１、ステップＴ２０１、ステップＴ２０２については、それぞれ、第１の実施形態のステップＳ１０１、ステップＳ２０１、ステップＳ２０２と同様であるので、以下ではステップＴ３０１以降の処理について説明する。
【０２８１】
（１）まず、ステップＴ３０１の線形計画問題表現部３５により行われる線形計画問題による表現を作成する処理について説明する。
【０２８２】
ステップＴ３０１では、ステップＴ１０１，Ｔ２０１，Ｔ２０２を経て作成された、入力データ格納用ファイルの不良ビットセルの位置情報およびスペアの適用範囲と本数制限を線形計画問題で表現する。
【０２８３】
一般に、２部グラフＧの最小被覆問題は次のように整数計画問題（ＩＰ）として定式化できる（例えば上記文献「情報の構造」に開示されている）。
【０２８４】
【数３】
0003581249.tif 000004
【０２８５】
ここで、ｎ，ｍはそれぞれＧの頂点数、辺数（すなわちラインフェイル処理終了後の不良ビットの総数）である。ＫはＧの接続行列であり、Ｉｍ  は全ての要素が１であるようなｍ桁の行ベクトルを表す。
【０２８６】
図３７（ａ）にステップＴ１０１，Ｔ２０１，Ｔ２０２を経て縮小された行列Ｂの一例を、図３７（ｂ）にこの行列Ｂに対応する２部グラフを、図３７（ｃ）にその行列Ｂを等価に表現する２部グラフＧの接続行列Ｋを示す。行列Ｂの行または列の番号（インデックス）が、２部グラフＧの頂点番号に対応している。なお、ここでは、行列Ｂの行または列の番号は、２部グラフＧの頂点番号を見易くするために、１から始まる通し番号を付けている。２部グラフＧの辺のラベルａ，ｂ，ｃ等は、行列Ｂの不良ビットに対応している。接続行列Ｋは２部グラフＧの頂点と辺の間の接続関係を表した行列である。
【０２８７】
２部グラフの最小被覆問題と最大マッチング問題は線形計画問題として眺めたとき互いに双対な問題であるため、上記式の２番目にある条件の部分を実数条件ｘｉ  ≧０（１≦ｉ≦ｎ）に置き換えて、線形計画問題として扱うことができる（例えば上記文献「情報の構造」に開示されている）。つまり、次の線形計画問題（ＬＰ）は最適解として整数解を持つ。
【０２８８】
【数４】
0003581249.tif 000005
【０２８９】
前述したように、最小被覆問題は、スペアの本数に制限がないとした場合の最適な救済解に相当するものである。
【０２９０】
スペアの本数に制限のある本来の不良ビットの救済問題においては、まず、入力データ格納用ファイルの不良ビットセルの位置情報をもとに、係数行列Ｋを作成する。次に、スペアの適用範囲と本数制限を線形不等式によって表現する。すると、次のような整数計画問題（ＲＩＰ）で表現できる。ただし、次に示すものは図１に例示した構造を対象とした場合の一例であり、実際には種々の制約条件に応じて異なったものとなる。
【０２９１】
【数５】
0003581249.tif 000006
【０２９２】
ここで、行列ＢはステップＴ２０２を経た後の縮小された行列Ｂであり、その行および列には１，２，３，…という通番が付けられているものとする。ｕ，ｄ，ｌ，ｒは行列Ｂのそれぞれ上行、下行、左列、右列の数でありｕ＋ｄ＋ｌ＋ｒ＝ｎである。ｉｄｘ（Ａ）は本来のメモリーブロック行列Ａの行、列に相当する行、列の番号からなる集合である。
【０２９３】
例えば、図３７の行列Ｂの場合、ｎ＝１４，ｍ＝１２，ｕ＝ｄ＝３，ｌ＝ｒ＝４，ｉｄｘ（Ａ）＝｛２，３，４，５，９，１０，１１，１２｝である。
【０２９４】
この整数計画問題（ＲＩＰ）の整数条件ｘｉ  （ｘｉ  は０または１），（１≦ｉ≦ｎ）を、実数条件ｘｉ  ≧０（１≦ｉ≦ｎ）に置き換えると、次のような線形計画問題（ＲＬＰ）が得られる。
【０２９５】
【数６】
0003581249.tif 000007
【０２９６】
（２）次に、ステップＴ４０１の２段階単体法適用部４５により行われる２段階単体法を適用して救済解を得る処理について説明する。
【０２９７】
ステップＴ４０１では、上記した線形計画問題（ＲＬＰ）に２段階単体法を適用する。２段階単体法は良く知られた線形計画問題（ＬＰ）の解法であり例えば文献「線形計画法」、今野浩著、日科技連に詳しく開示されている。
【０２９８】
この線形計画問題（ＲＬＰ）は前述した線形計画問題（ＬＰ）と違い、最適解として整数解を持つ保証はないが、ラインフェイルの救済後の不良ビットが、どの行、どの列にも一様に発生する傾向のある実際のＲＡＭデータにおいては整数解が得られる場合が非常に多い。また、整数計画問題（ＲＩＰ）はスペアの本数に制約のある本来の不良ビットの救済問題を等価に定式化したものなので、線形計画問題（ＲＬＰ）が整数解を持つ場合は、それは常に最適な救済解であることになる。
【０２９９】
２段階単体法のフェーズ１（第１段階）において線形計画問題（ＲＬＰ）に実行可能解が存在しないことが判明した場合は、ステップＴ７０２に移る。また、２段階単体法の出力結果が非整数解の場合は、ステップＴ７０３に移る。
【０３００】
図３７の行列Ｂに２段階単体法を適用すると、ｘ１  ＝ｘ４  ＝ｘ７  ＝ｘ１０＝ｘ１３＝ｘ１４＝１、他のｘｉ  については０という結果が得られる。そのときの目的関数の値は２である。ただし、もとの行列Ａには上水平、下水平、左垂直、右垂直スペアがそれぞれ３本ずつあるとしている（なお、前述したように、図３７の行列Ｂはラインフェイルや、零行、零列を削除して縮小された後の行列である）。
【０３０１】
（３）次に、ステップＴ７０１の救済結果出力部７０による救済の対応データを作成し出力（あるいは送信）する処理について説明する。
【０３０２】
ステップＴ７０１では、ステップＴ４０１で得られた救済解（行列Ｂの不良ラインとＢのスペアの間の対応関係）をもとに、本来のメモリーブロック（行列Ａ）の不良ラインと本来のスペアの間の対応関係を求める。
【０３０３】
第１の実施形態のステップＳ７０１で述べたように、行列Ｂの救済解において、ＢのスペアがＡのスペアを救済している（に対応している）場合は、そのＡスペアはＡの不良ラインの救済には使用しない。ＢのスペアがＡの不良ラインを救済している場合は、使用しないことが決まったＡスペア以外のＡスペアを任意に割り当てる。
【０３０４】
以上の方法で定めた救済の対応データを出力する。
【０３０５】
図３７の行列Ｂの例では、行ラベル４の行と、列ラベル１０の列が救済されるべき不良ラインとして検出される。行ラベル１の行と、列ラベル７，１３，１４の列は、いずれもＡスペアであるので、これらはＡの不良ラインの救済には使用しない。
【０３０６】
行列Ａの不良ラインと本来のスペアの間の対応関係を求めるには、行ラベル４の行にＡの任意の下水平スペアを割り当て、列ラベル１０の列にＡの「列ラベル７の左垂直スペア」以外の左垂直スペアを割り当てればよい。
【０３０７】
なお、前述したように広い意味での救済解を出力するようにしてもよい。
【０３０８】
（４）次に、ステップＴ７０２の救済結果出力部７０による救済不可を出力（あるいは送信）する処理について説明する。
【０３０９】
ステップＴ７０２では、スペア数が不足した場合は救済不可として、その旨メッセージを出力する。
【０３１０】
（５）次に、ステップＴ７０３の救済結果出力部７０により行われる非整数解による救済不可を出力（あるいは送信）する処理について説明する。
【０３１１】
ステップＴ７０３では、ステップＴ４０１で非整数解が得られた場合は、救済不可として、その旨を示すメッセージを出力する。
【０３１２】
ところで、以上では非整数解となった場合に救済不可としたが、その代わりに、ステップＴ４０１で非整数解となった場合に、全ての不良ビットを救済できる解が存在する可能性があるので、整数解を得るためのさらなる手順を実行もしくは試行するようにしてもよい。
【０３１３】
なお、上記では整数計画問題を線形計画問題に緩和して解く方法について説明したが、例えば文献「整数計画法と組み合わせ最適化」（今野浩著、日科技連）に開示されている分枝限定法等を用いてもよい。
【０３１４】
以上、各実施形態について、図１のメモリーブロックと予備ラインの配置モデルを用いて説明してきたが、前述したように本発明は前記モデルに限定されるものではない。例えば、図３８のようなモデルも自然な拡張で扱うことが可能である。図３８のモデルでは、１または複数のスペアからなる垂直スペアのグループＧｉ  は垂直ラインのブロックＢｉ  の救済に使われ、１または複数のスペアからなる水平スペアのグループＧＡ  ，ＧＢ  はそれぞれ水平ラインのブロックＢＡ  ，ＢＢ  の救済に使われる。そして、互いに直交するスペアの使用に制約を与えるリンボが設定されている。このモデルに対しても前述した定理が成り立つため、本発明を適用することができる。
【０３１５】
また、これらのモデルにおいては、スペアやリンボはメモリーブロックの外側に位置するように配置されているが、スペアやリンボは例えばメモリーブロック内の２つの小ブロックの間に配置されていてもよいし、あるいは小ブロックの内部に配置されていてもよい。例えば、図１の場合、メモリーブロック行列Ａの左列（ＢＬＫ１とＢＬＫ２からなる部分）の中央にＲ１，…，Ｒ６をまとめて挿入し、Ａの右列（ＢＬＫ３とＢＬＫ４からなる部分）の中央にＲ７，…，Ｒ１２をまとめて挿入し、Ａの上行（ＢＬＫ１とＢＬＫ３からなる部分）の下側にＣ１，Ｃ２，Ｃ３をまとめて挿入し、Ａの下行（ＢＬＫ２とＢＬＫ４からなる部分）の下側にＣ４，Ｃ５，Ｃ６をまとめて挿入してもよい。その場合、リンボは互いに直交するスペアの見掛け上交差する位置に配置されることになる。このような変形は、もとの図１から簡単なアドレスの付け替えによって得ることができる。
【０３１６】
また、上述したモデルにおいては、スペアにはその本数とその割り当て可能範囲という制約しか与えられていないが、その他にも種々の制約が設けられている場合があり得る。例えば、後述する同じ番号列へのスペアの割り当て禁止、あるいは２つのアドレスの２進表現におけるビット列の差異に関する制約等がある。これらは大規模なメモリーの不良ビット検出および救済をコンパクトに扱うための、いわゆるアドレス圧縮等の技術と関連する。
【０３１７】
例えば、図１において行列Ａの左列、右列にそれぞれ１，２，３，…という通番を付けた場合、同じ番号を持つ２つの列（例えば右列の番号１０の列と左列の番号１０の列）に対して、共に垂直スペアを割り当てることは禁止するという制約が設けられている場合がある。
【０３１８】
このようなスペアの使用に関する制約が与えられている場合にも、本実施形態は適用可能である。例えば、第１の実施形態の場合、ステップＳ６０２，Ｓ６０３のサイクル（あるいはステップＳ６０１も含めたＳ６０１〜Ｓ６０３のサイクル）を複数回繰り返し、複数の解候補を求めて、それら解候補の各々に対してスペアの使用に関する制約を満たしているか否かをチェックし、満たしているものを救済解として出力することも可能である。第２の実施形態の場合は、制約条件を等式あるいは不等式で表現して（ＲＩＰ）の条件に付加すればよい。ただし、一般に条件数が増えるとそれだけ整数解が求まる可能性は小さくなる。
【０３１９】
また、本発明は、メモリーブロックがサブブロックに分割されておらずスペアの使用にメモリブロックに関する制限のないものにも適用可能である。この場合、スペアについては水平と垂直の２分類になり、孤立不良ではグループが１つになるなど、サブブロックに関する処理や内部データが修正されるだけである。もちろん、メモリーブロックが行または列のいずれかの方向のみに分割されたサブブロックが存在する場合にも同様に適用可能である。
【０３２０】
また、上記の他、本発明は様々なモデルに、そのまま、もしくは部分的に適用可能である。
【０３２１】
また、本実施形態においては、メモリーブロック行列Ａの不良救済問題を、行列Ａにスペアとリンボを全て添付して拡大した行列Ｂの不良救済問題に拡張して考えるという方法を、ＤＭ分解や線形計画法と結びつけて説明したが、この拡張するという考え方は他の従来手法と結び付けることも可能である。例えば、文献“Ｅｆｆｃｉｅｎｔ  ｓｐａｒｅ  ａｌｌｏｃａｔｉｏｎ  ｆｏｒ  ｒｅｃｏｎｆｉｇｕｒａｂｌｅ  ａｒｒａｙｓ”，ｂｙ  Ｓｙ−Ｙｅｎ  Ｋｕｏ  ａｎｄ  Ｗ．Ｋｅｎｔ  Ｆｕｃｈｓ，  ＩＥＥＥ  Ｄｅｓｉｇｎ  ａｎｄ  Ｔｅｓｔ，  ｐｐ．２４−３１，１９８７で提案されているｂｒａｎｃｈ−ａｎｄ−ｂｏｕｎｄ  ａｌｇｏｒｉｔｈｍやｈｅｕｒｉｓｔｉｃ  ａｌｇｏｒｉｔｈｍを行列Ｂに適用してＢの救済解を求め、その救済解をもとに行列Ａの不良ラインと本来の（行列Ａの）スペアの間の対応関係を求めることも可能である（すなわち上記アルゴリズムを本実施形態に係る救済処理として用いる）。
【０３２２】
また、各実施形態においては、行列Ｂの不良救済問題を解いてから、行列Ａの救済解を求めるという方法を説明したが、逆に行列Ａの救済解の候補を求めてから、前記候補を行列Ｂの救済解に拡張してみて、当該候補が実際に行列Ａの救済解になり得るか否かをチェックしてみるという方法も可能である。つまり、前述した定理の（必要性）の証明において示した方法と同様の方法で、行列Ａの救済解候補の救済ライン集合で救済されるＡの不良ラインの集合を、行列Ｂの救済ライン集合で救済されるＢの不良ラインの集合へと拡張してみる。
【０３２３】
行列Ａの救済解の候補（αとおく）を求める際は、行列Ａのスペアやリンボには不良ビットが存在しないものと仮定して求める。救済解の候補αを行列Ｂの救済解へと拡張する際には、まず、行列Ｂから、行列Ａの救済解の候補の行と列を行列Ｂまで延長して得られる行と列を削除する。そして、この削除によって縮小された行列（Ｂ／αとおく）の不良救済問題を解く。行列Ｂ／αの不良救済問題においては、前記候補αで使用していたスペア数の残数を用いて、スペアやリンボには不良ビットが存在しないものとして解く。
【０３２４】
もし行列Ｂ／αの救済解が求まれば、前記候補αは行列Ａの救済解になり得るので、行列Ａの不良ラインと本来のスペアの間の対応関係を定めてやればよい。もし前記候補αが行列Ｂの救済解へと拡張できなかった場合は、行列Ａの救済解の候補を求め直して、再度、拡張を試みればよい。
【０３２５】
図３９（ａ）〜（ｄ）に具体例を示す。まず、行列Ａの救済解の候補α（図３９（ａ）の長円で囲った２本のライン）を作成し、その救済ラインによって救済される各ラインをＢのサイズに引き延ばして除去する（図３９（ｂ））。次に、その除去によって発生する零行、零列を取り除いて圧縮した行列Ｂ／αの救済解を前記候補αで使用していたスペア数の残数を用いて求める（図３９（ｃ））。その救済解をαと合わせれば、元の行列Ｂの救済解となる（図３９（ｄ））。行列Ａの不良ラインと本来のスペアの間の対応関係は、図３９（ｄ）から自明である（長円で囲まれていない２本のスペアをαの２本ラインに割り当てればよい）。
【０３２６】
さて、以上では１つの半導体デバイスの１チップ内の１つのメモリーブロックに対する処理を中心に説明を行ったが、ここで、１チップ単位の処理、１ウエハ単位の処理、１ロット単位の処理に関連した構成について説明する。
【０３２７】
通常、メモリーテスタ装置では、ウエハ（半導体基板）の状態でテストを行い、リペア装置では、ウエハの状態でリペアを行う。従って、その中間の工程に位置する半導体不良ビット救済処理装置の場合、最低限１枚のウエハを単位として処理が行われる。また、通常、製造工程では、２５枚などを１組とするロットを単位としてプロセスが進められることが多い。また、多品種の製造ラインにおいては、ある半導体不良ビット救済処理装置が、複数品種に係る半導体デバイスを担当する場合もある。
【０３２８】
従って、半導体不良ビット救済処理装置には、例えば、サブブロックごとの不良ビットの情報とともに、全体的な製造支援システムとリンクされたロットＩＤ、ロット内のウエハ番号、ウエハ内におけるチップ番号、チップ内におけるサブブロック番号などが与えられる場合がある。また、例えば、ロット毎にそのロットの品種ＩＤが与えられる場合がある。
【０３２９】
このような場合、半導体不良ビット救済処理装置には、例えば、図４０（ａ）に示すような形式でデータを与えるようにすればよい。なお、メモリーテスタ側でラインフェイル処理を行う場合には、例えば、図４０（ｂ）に示すような形式となる。そして、半導体不良ビット救済処理装置は、同様の形式でデータを出力すればよい。なお、救済不可のチップについてはブロックＩＤ等のデータは不要となる。
【０３３０】
また、半導体デバイスの品種によって、上水平スペア等の数が相違し、あるいはサブブロックの分割方法、スペアに関する制約等が相違することがあるので、半導体不良ビット救済処理装置は、例えば、図４０（ｃ）に示すような、品種ＩＤをキーとして、ウエハに関するデータ、チップに関するデータ、ブロックに関するデータなどを登録したテーブルを持ち、与えられたロットＩＤから処理に必要な情報を検索し、処理に先だって必要な設定をしておく。例えば、図１６の例で言えば、４種類のスペアの残数を、検索によって得た数値からそれぞれ３本と設定する。なお、上記のようなテーブルを持たずに、必要時にネットワーク等で接続されたサーバ等からロットＩＤをキーとして得るようにしてもよい。
【０３３１】
また、製造ラインにおいては、通常、チップ単位でのリペアに意味があるので、１つでも救済不可のメモリーブロックが見つかれば、その時点で当該チップの救済処理を打ち切るような処理を行うのが好ましい。
【０３３２】
また、１チップには通常複数のメモリーブロックが含まれるので、処理時間を削減するために、本半導体不良ビット救済処理装置（あるいはＣＰＵ）を複数台並列に設け、１ラウンドで複数のメモリーブロックについて同時に救済解を求めるようにしてもよい。
【０３３３】
次に、本実施形態に係る半導体不良ビット救済処理装置のシステム構成について説明する。
【０３３４】
本半導体不良ビット救済処理装置は、ソフトウエアで実現可能であり、図４１（ａ）に示すようにメモリーテスタ装置３０１やリペア装置３０３とは独立した１つの装置３０２として実現する他に、図４１（ｂ）に示すようにメモリーテスタ装置３０４上に実現する方法、図４２（ａ）に示すようにリペア装置３０７上に実現する方法、図４２（ｂ）に示すようにメモリーテスタ装置３０８とリペア装置３０９に機能を分散して実現する方法（例えばメモリーテスタ装置側で行列Ｂに対する救済解を求め、これを中間情報としてリペア装置に与え、リペア装置側で行列Ａに対する救済解に変換する）、図４１（ａ）において一部の機能を分散して実現する方法等、種々の実現形態が可能である。
【０３３５】
また、メモリーテスタ装置と半導体不良ビット救済処理装置とが１対多、多対１、あるいは多対多に対応する構成、リペア装置と半導体不良ビット救済処理装置とが１対多、多対１、あるいは多対多に対応する構成も可能である。この場合、受け渡しする情報には、必要な装置ＩＤを付加すればよい。
【０３３６】
次に、図４３に本半導体不良ビット救済処理装置をソフトウエアで実現する場合の装置構成の一例を示す。
【０３３７】
本半導体不良ビット救済処理装置の処理をＣＰＵ３２１に実行させるためのプログラムは、例えば、これを格納した記録媒体から読み取り装置を介し、あるいは他の計算機等から通信回線を介し通信インタフェース装置を通じるなどしてハードディスク装置３２３にインストールされ、実行時には適宜ＲＡＭ３２２に書き込まれて、ＣＰＵ３２１により実行される。
【０３３８】
図４１（ａ）や図４２（ａ）の場合、入力装置３２４は、例えば、通信手段等からなり、図４１（ｂ）や図４２（ｂ）の場合、例えば、入力装置３２４の代わりに、メモリーテスタ機能との間でのプロセス間通信が行われる。同様に、図４１（ａ）や図４１（ｂ）の場合、例えば、出力装置３２５は通信手段等からなり、図４２（ａ）や図４２（ｂ）の場合、例えば、出力装置３２５の代わりに、リペア機能との間でのプロセス間通信が行われる。
【０３３９】
また、図４０（ｃ）で説明したような各種情報は、例えば、ハードディスク装置３２３に格納され、必要に応じて参照され、あるいは通信装置によりネットワークを介して必要に応じて入手される。
【０３４０】
なお、メモリーテスト装置において、複数回（例えば数回ないし２０数回）のファンクションテストを行う場合に、ファンクションテストの間に救済処理を行い、救済不可となったチップについては以降のファンクションテストを行わないようにするものがあるが、本発明はこのようなシステムにも適用可能である。
【０３４１】
次に、本発明の第３の実施形態について説明する。
【０３４２】
本実施形態は、第１の実施形態の構成と第２の実施形態の構成を兼ね備え、第１の実施形態におけるＤＭ分解等による救済処理（すなわち高速で最適解またはこれに近い解を得ることができる救済処理）を、第２の実施形態における整数計画問題あるいは線形計画問題による救済処理（すなわち解が得られたならば、その解は必ず最適解であるような救済処理）でバックアップするものである。
【０３４３】
すなわち、第１の実施形態のようにＤＭ分解およびその縮約グラフにもとづいて救済解を求める場合に、制約時間内に救済解が求まらないときに、一旦処理を中止し、第２の実施形態のように整数／線形計画問題として救済解を求めることを行う。この場合、本実施形態をソフトウェアを用いて実現するならば、整数／線形計画問題の計算処理は、第１の救済処理等に用いるために用意されたプロセッサ（ＣＰＵ）ではなく別のプロセッサによって特別に処理するのが望ましい。このようにすることで、制約時間内にＤＭ分解およびその縮約グラフにもとづいて救済解が求まらない場合が少ないとき、整数／線形計画問題として時間をかけて救済解を求めることで、救済不可を削減できる。あるいはまた、制約時間内にＤＭ分解およびその縮約グラフにもとづいて救済解が求まらない場合が希なときには、ＤＭ分解およびその縮約グラフにもとづいて求めた救済解に最適性が保証されないときに整数／線形計画問題として最適な救済解を求めるためにもしくはＤＭ分解およびその縮約グラフにもとづいて求めた救済解の最適性を検証するために利用することもできる。
【０３４４】
図４４に、本実施形態に係る半導体不良ビット救済処理装置の概略構成を示す。
【０３４５】
本半導体不良ビット救済処理装置は、データ入力部１０、ラインフェイル判定部２０、第１の救済処理部１００、第２の救済処理部２００、救済結果出力部７０を備えている。
【０３４６】
データ入力部１０、ラインフェイル判定部２０、救済結果出力部７０については第１の実施形態と同様である。なお、第１の実施形態や第２の実施形態と同様にラインフェイル判定部２０を設けない構成もあるが、以下ではラインフェイル判定部２０を設けるものとして説明する。
【０３４７】
第１の救済処理部１００は、第１の実施形態における２部グラフ作成部３０、最大マッチング作成部４０、ＤＭ分解作成部５０、救済解作成部６０に相当する処理を行うものである。
【０３４８】
第２の救済処理部２００は、第２の実施形態の線形計画問題表現部３５、２段階単体法適用部４５に相当する処理を行うものである。
【０３４９】
本実施形態は、ソフトウェアにより実現可能である。第１の救済処理部１００を割り当てるＣＰＵと第２の救済処理部２００を割り当てるＣＰＵとを同じ性能のものにしてもよいし、第１の救済処理部１００を割り当てるＣＰＵよりも第２の救済処理部２００を割り当てるＣＰＵの方を計算速度に関して高性能なものとしてもよい。
【０３５０】
本実施形態では、第１の救済処理部１００による処理には、１単位の処理に対する制限時間（ｔ１とする）が設けられるものとする。なお、第２の救済処理部２００による処理には、制限時間（ｔ２とする）を設ける方法と、制限時間を設けない方法とがある。また、前者の場合、制限時間ｔ２を制限時間ｔ１よりも長く設定する方法（例えば第１の救済処理部１００に割り当てるＣＰＵと第２の救済処理部２００に割り当てるＣＰＵとを同じ性能のものにする場合）と、制限時間ｔ１と制限時間ｔ２を同じに設定する方法（例えば第１の救済処理部１００に割り当てるＣＰＵよりも第２の救済処理部２００を割り当てるＣＰＵの方を計算速度に関して高性能なものとする場合）とが考えられる。
【０３５１】
また、救済処理を繰り返して行う場合、第１の救済処理部１００と第２の救済処理部２００による処理の開始や終了を同期して行う方法と、第１の救済処理部１００は周期的に実行するが、これには第２の救済処理部２００を同期させない方法とがある。
【０３５２】
図４５に、本半導体不良ビット救済処理装置の処理手順の一例を示す。ただし、図４５では、第１の実施形態や第２の実施形態と相違する部分のみを示している。
【０３５３】
まず、第１の実施形態や第２の実施形態と同様に、不良ビットのアドレスデータの読み込み、ラインフェイルの算出などの処理を行う。
【０３５４】
次に、第１の救済処理部１００により、第１の実施形態と同様にして、救済解を求めるための処理を行う。
【０３５５】
次に、本実施形態では、所定の条件が成立した場合には、第２の救済処理部２００により、第２の実施形態と同様にして、救済解を求めるための処理を行う。
【０３５６】
上記の所定の条件としては、種々のものがある。
【０３５７】
第１の形態は、第１の救済処理部１００によっても、規定の制限時間内に救済解を求めることができなかった場合に、第２の救済処理部２００を起動するものである。
【０３５８】
第２の形態は、第１の救済処理部１００によって規定の制限時間内に救済解を求めることができないことがまれであるような場合に、第１の救済処理部１００によっても、規定の制限時間内に救済解を求めることができなかったならば、第２の救済処理部２００を起動するものである。
【０３５９】
第３の形態は、第１の救済処理部１００によって求められた救済解の最適性を検証するために、第２の救済処理部２００によって最適解を求めるための処理を行うものである。
【０３６０】
第４の形態は、第１の救済処理部１００によって規定の制限時間内に救済解を求めることができないことがまれであるような場合に、第１の救済処理部１００によって求められた救済解の最適性を検証するために、第２の救済処理部２００によって最適解を求めるための処理を行うものである。
【０３６１】
なお、制限時間内に救済解を求めることができなかったとは、処理中に制限時間を経過してしまったことを意味し、制限時間内にスペア不足が判明するなどして救済解がないことが分かった場合は含まれない。
【０３６２】
そして、いずれの形態においても、第１の救済処理部１００のみ実行され、救済解が得られた場合には、その救済解を出力し、第１の救済処理部１００および第２の救済処理部２００の両方が実行され、救済解が得られた場合には、第２の救済処理部２００の救済解を出力し、救済解が得られなかった場合には、救済不可を示す旨のメッセージを出力する。また、複数の救済処理が並列実行された場合には、上記の救済解やメッセージとともに救済対象の識別情報が出力される。
【０３６３】
なお、第１の救済処理部１００および第２の救済処理部２００の両方が実行され、救済解が得られた場合には、第１の救済処理部１００が最適解であったか否かを示す情報を併せて出力するようにしてもよい。
【０３６４】
また、救済解が得られなかった場合には、第２の救済処理部２００が実行されたか否か、救済解なしとなった理由がスペア数不足か時間不足か非整数解かなどを示す情報を出力するようにしてもよい。
【０３６５】
以上の様々な観点での種々の構成は、本半導体不良ビット救済処理装置の目的、例えば製造ラインへ設置するのか、研究もしくは不良ＩＣの詳細解析などのオフライン的なサイトに設置するのか、などに応じて、適宜選択することができる。
【０３６６】
次に、本実施形態に係る半導体不良ビット救済処理装置を製造ラインへ設置することを想定した場合の一例について説明する。
【０３６７】
図４６は、並列実行するｍ系統の第１の救済処理部１００−１〜１００−ｍと、１系統の第２の救済処理部２００を備えた半導体不良ビット救済処理装置の例である。なお、データ入力部１０とラインフェイル処理部２０と救済結果出力部７０は省略してある。
【０３６８】
ここでは、各第１の救済処理部１００−１〜１００−ｍと第２の救済処理部２００に専用のＣＰＵが割り当てられるものとする。
【０３６９】
第１の救済処理部１００−１〜１００−ｍによる第１の救済処理は、同時に実行開始され、規定の制限時間に達したら、同時に終了されるものとする。制限時間内に救済解が得られた第１の救済処理部は、制限時間に達するまで待ち状態となり、制限時間内に救済解が得られなかった第１の救済処理部は、制限時間にて処理を打ち切ることになる。
【０３７０】
そして、制限時間内に救済解が得られた第１の救済処理部からは救済解が出力され、制限時間内に救済解がないことが判明した第１の救済処理部からは救済不可である旨を示すメッセージが出力され、制限時間内に救済解が得られなかった第１の救済処理部からは、第２の救済処理の結果を待たせるために保留を示す旨のメッセージを出力する。なお、複数の救済処理が並列実行された場合には、上記の救済解やメッセージとともに救済対象の識別情報が出力される。
【０３７１】
そして、救済対象のデータがｍセット以上ある場合には、第１の救済処理部１００−１〜１００−ｍによる第１の救済処理が繰り返し実行される。
【０３７２】
ここで、制限時間内に救済解が得られなかった第１の救済処理部があった場合には、その救済対象データに対して第２の救済処理部２００による第２の救済処理を試みる。
【０３７３】
そして、第２の救済処理部からは、制限時間内に救済解が得られたならばその救済解が出力され、制限時間内に救済解がないことが判明した場合および制限時間内に救済解が得られなかった場合には、救済不可を示すメッセージが出力される。
【０３７４】
解の統合処理部３００では、第１の救済処理部から保留を示す旨のメッセージを受けた対象（識別情報）について、その後に第２の救済処理部から受けた結果（救済解または救済不可メッセージ）をもって、最終結果とする。
【０３７５】
なお、この解の統合処理部３００は、本半導体不良ビット救済処理装置内に設けられる場合と、リペア装置側に設けられる場合とが考えられる。
【０３７６】
次に、図４７を参照しながら処理の流れの具体例を示す。
【０３７７】
ここでは、図４７に示すように、第１の救済処理部１００−１〜１００−８にはそれぞれＣＰＵ１〜８が割り当てられ、第２の救済処理部２００にはＣＰＵ９が割り当てられており、一定周期で同期して１単位の救済対象ごとに処理を進めていく。また、第２の救済処理部の処理には、第１の救済処理部の２単位分の周期が割り当てられるものとする（この時間内に計算が終了するものとする）。
【０３７８】
まず、第１回目の周期においては、ＣＰＵ１〜ＣＰＵ８においてそれぞれ救済対象＃１〜＃８に対する第１の救済処理が実行される。
【０３７９】
ここで、救済対象＃３に対する第１の救済処理を行ったＣＰＵ３において処理途中で制限時間に達してしまって救済解が得られなかった場合、救済対象＃３に対する第２の救済処理がＣＰＵ９において実行されることになる。
【０３８０】
しかして、第２回目の周期においては、ＣＰＵ１〜ＣＰＵ８においてそれぞれ救済対象＃９〜＃１６に対する第１の救済処理が実行され、第３回目の周期においては、ＣＰＵ１〜ＣＰＵ８においてそれぞれ救済対象＃１７〜＃２４に対する第１の救済処理が実行されるとともに、第２回目と第３回目の周期に渡って、ＣＰＵ９において救済対象＃３に対する第２の救済処理が実行される。
【０３８１】
そして、第４回目の周期においては、ＣＰＵ１〜ＣＰＵ８においてそれぞれ救済対象＃２５〜＃３２に対する第１の救済処理が実行されるとともに、他に処理途中で制限時間に達してしまって救済解が得られなかった救済対象があれば、その救済対象に対する第２の救済処理がＣＰＵ９において実行される。
【０３８２】
また、例えば、上記において、第１の救済処理により救済解が得られないことがまれでＣＰＵ９がほとんど稼働しないような場合には、第１の救済処理により救済解が得られたいずれかの救済対象について、ＣＰＵ９を用いて第２の救済処理を行うことによって、第２の救済処理で得た最適解と第１の救済処理で得た救済解とを比較することによって、第１の救済処理で求めた解の最適性を検証するようにしてもよい。
【０３８３】
次に、本発明の第４の実施形態について説明する。
【０３８４】
これまでは、各スペアが１本のラインとして割当てられるようなメモリーブロックに対する不良ビットの救済処理について説明してきた。すなわち、各垂直スペアや各水平スペアはメモリーブロックの行方向や列方向と同じビット幅を持ち、各スペアは１本を単位として（すなわちその行方向や列方向と同じビット数を単位として）用いられるものであった。
【０３８５】
本実施形態では、各スペアを１本のラインとして割当てなくても良いような自由度の存在するメモリーブロックに対する不良ビットの救済処理について説明する。
【０３８６】
まずその説明に先だって、これまで説明してきた種々の救済処理が適用可能なメモリーブロックとスペアとリンボの構成について言及しておく。
【０３８７】
ここでは、メモリーブロックをメイン、垂直スペアをＲスペア、水平スペアをＣスペアと呼ぶものとする。通常、メインは複数のブロックに分かれ、それぞれのブロックに対して数本ずつのスペアが使用可能という仕様になっている。そして、実際、スペアはメイン内のブロックの任意の箇所に埋め込まれている場合が多い。メインのうちブロックを垂直方向に分割したときのそれぞれの部分をＲブロック、水平方向に分割したときのそれぞれの部分をＣブロックと呼ぶ。
【０３８８】
図４８にメモリーブロックとスペアとリンボの構成の一例を示す。この例では、ＢＬＫ−１とＢＬＫ−２がそれぞれＲブロックであり、ＢＬＫ−ＡとＢＬＫ−ＢがそれぞれＣブロックである。Ｒスペア（１）はＢＬＫ−１の不良ビットを救済するためのＲスペア群であり、Ｒスペア（２）はＢＬＫ−２の不良ビットを救済するためのＲスペア群である。Ｃスペア（Ａ）はＢＬＫ−Ａの不良ビットを救済するためのＣスペア群であり、Ｃスペア（Ｂ）はＢＬＫ−Ｂの不良ビットを救済するためのＣスペア群である。図４８ではＲスペアはＲブロックの右側に、ＣスペアはＣブロックの下側に書いてあるが、ＲスペアがＲブロックの内部に埋め込まれていたり、ＣスペアがＣブロックの内部に埋め込まれている例もある。
【０３８９】
前述したように、スペアは、メインの行、列の間に埋め込まれている場合が多いが、アドレス変換をすれば、例えば図４９のようにメインの外側に設けられているような形で表現することができる。その場合、リンボは、ＲスペアとＣスペアの交差する部分として、メインの外側に現れる。
【０３９０】
ここで、救済解を求める処理を行う対象とする処理単位が以下の条件を満たす場合、この処理単位は「基本形」であると定義する。
条件：「各スペアは１本のラインとして割当てられる。」
この条件はより具体的に言うと、「垂直方向の予備ラインはメモリーブロックの垂直方向の長さを持つ１本のラインとして垂直方向の所与の１つまたは複数のブロックに属す不良ラインに割当て可能であり、かつ、水平方向の予備ラインはメモリーブロックの水平方向の長さを持つ１本のラインとして水平方向の所与の１つまたは複数のブロックに属す不良ラインに割当て可能である」という条件である。
【０３９１】
なお、図４９の例のようにスペアやリンボを外側に記述するのは、単に構造を見易くするためであり、このような記述自体は基本形の本質とは無関係である。
【０３９２】
さて、先に証明した定理すなわち「行列Ａの救済解が存在するための必要十分条件は、行列Ｂの救済解が存在することである。」という定理は、基本形に変換できる処理単位に対して常に成り立つ（先の例では、Ｒブロック数が２、Ｃブロック数が２の場合について上記定理を証明したが、この定理がブロック数に依存せずに成り立つことは明らかである）。従って、これまで説明してきた種々の救済処理は、基本形に変換できる任意の処理単位に対して利用できるものである。
【０３９３】
救済処理を実現するための救済プログラムは、基本形に変換できるどのような処理単位に対しても適用できるように、汎用化してもよい。その場合、ブロックのサイズやスペア数等、デバイスに固有なパラメータは外から、例えばファイル形式で渡してもよい。
【０３９４】
さて、処理単位のなかには、上記した条件を満足せず、そのままでは基本形にならない場合もある。基本形にならないということは、その処理単位にはこれまで説明してきた種々の救済処理救済処理をそのまま適用することができないということを意味する。
【０３９５】
例えば、図５０に例示するメモリーブロックとスペアとリンボの構成は、Ｃスペアを細分化して割当てることができるという自由度の高いデバイスの処理単位の例である。すなわち、Ｒスペアに限っては上記条件を満足しているが、Ｃスペアが上記条件を満足していない場合である。
【０３９６】
以下では、Ｃスペアを細分化して割当てることができる例をもとに説明するが、Ｒスペアを細分化して割当てることができる例に対しても同様のことが言える。なお、ＣスペアおよびＲスペアのいずれも細分化して割当てることができる場合については後で詳しく説明する。
【０３９７】
図５０の例においては、Ｓ０〜Ｓ７の８つのブロックからなるメインを囲むように、左右４本ずつのＲスペアと上下３本ずつのＣスペアと必要なリンボが配置されている（実際に図５０のような構成になっていてもよいし、アドレス変換後の配置が図５０のようであってもよい）。
【０３９８】
ＲブロックであるＢＬＫ−１はブロックＳ０，Ｓ１，Ｓ４，Ｓ５を含み、ＲブロックであるＢＬＫ−２はブロックＳ２，Ｓ３，Ｓ６，Ｓ７を含み、ＣブロックであるＢＬＫ−ＡはブロックＳ０，Ｓ１，Ｓ２，Ｓ３を含み、ＣブロックであるＢＬＫ−ＢはブロックＳ４，Ｓ５，Ｓ６，Ｓ７を含む。
【０３９９】
左側の４本のＲスペア（Ｒ１とする）はＢＬＫ−１用であり、右側の４本のＲスペア（Ｒ２とする）はＢＬＫ−２用であるものとする。また、上側の３本のＣスペアはＢＬＫ−Ａ用であり、下側の４本のＣスペアはＢＬＫ−Ｂ用であるものとする（なお、上下のそれぞれのＣスペアについて、Ｓ０とＳ４に対応する部分をｃ１、Ｓ１とＳ５に対応する部分をｃ２、Ｓ２とＳ６に対応する部分をｃ３、Ｓ３とＳ７に対応する部分をｃ４と呼ぶものとする）。
【０４００】
これらＲスペアはそれぞれ、１本のラインとして割り当てられる。
【０４０１】
一方、Ｃスペアについては、実際の割当てにおいては、１本のＣスペアを４当分して、その一部だけを使うことが可能であるものとする。また、ここでは、それら細分化された４本の短いＣスペアには、他の短いＣスペアと連動して用いなければならないという制約があるものとする。例えば、｛ｃ１，ｃ２，ｃ３，ｃ４｝をそれら４本の短いＣスペアとしたとき、｛ｃ１，ｃ３｝，｛ｃ２，ｃ４｝は、それぞれメインの同一の行アドレスを救済しなければならないという制約である。つまり、短いＣスペアは１つおきに２本ずつ１本にまとめた状態で使用しなければならないという制約である（実質的には１本のＣスペアを２当分して、その一部だけを使うことが可能であるということになる）。
【０４０２】
このような場合には、上記の連動という性質を用いてメインとＣスペアを縦方向に分割し、図５１の（ａ）と（ｂ）のような２つの部分処理単位に分けて扱うことにする。なお、左右のＲスペア（Ｒ１，Ｒ２）は、両方の部分処理単位で共用させる。各部分処理単位においてはＲスペアを共用するため、この部分処理単位を「共用単位」と呼ぶことにする。共用単位においては、スペアが１本のラインとしてメインのラインを救済するという対応関係が付けられているため、上記条件を満足し、共用単位は基本形になっていることがわかる。
【０４０３】
次に、上記条件を満足しない他の例を示す。
【０４０４】
図５２に例示するメモリーブロックとスペアとリンボの構成は、Ｃスペアの割当て範囲にさらに自由度のある例である。
【０４０５】
ＲスペアやＲブロックについては図５０の例と同様である。
【０４０６】
ＢＬＫ−ＡとＢＬＫ−Ｂは水平方向のブロック（Ｃブロック）、ＢＬＫ−１とＢＬＫ−２は垂直方向のブロック（Ｒブロック）を表す。Ｃブロックをさらに３つのＣサブブロックに分割し、ＢＬＫ−ＡのＣサブブロックはＢＬＫ−Ａ１、ＢＬＫ−Ａ２、ＢＬＫ−Ａ３で表し、ＢＬＫ−ＢのＣサブブロックはＢＬＫ−Ｂ１、ＢＬＫ−Ｂ２、ＢＬＫ−Ｂ３で表す。６本のＣスペアを上から順にＣＡ１、ＣＡ２、ＣＡ３、ＣＢ１、ＣＢ２、ＣＢ３で表す。
【０４０７】
Ｃスペアの細分化や連動という性質は図５０の例の場合と同様とする。図５０の例の場合と相違するのは、Ｃスペアの割当て範囲である。各Ｃスペアの割当て範囲は次のように重複しているものとする。すなわち、ＢＬＫ−Ａについては、ＣＡ１はＢＬＫ−Ａ２およびＢＬＫ−Ａ３の救済に、ＣＡ２はＢＬＫ−Ａ１およびＢＬＫ−Ａ３の救済に、ＣＡ３はＢＬＫ−Ａ１およびＢＬＫ−Ａ２の救済に使用可能である。ＢＬＫ−Ｂについても同様に、ＣＢ１はＢＬＫ−Ｂ２およびＢＬＫ−Ｂ３の救済に、ＣＢ２はＢＬＫ−Ｂ１およびＢＬＫ−Ｂ３の救済に、ＣＢ３はＢＬＫ−Ｂ１およびＢＬＫ−Ｂ２の救済に使用可能である。
【０４０８】
このような場合にも、図５０と同様に処理単位を２つの共用単位に分割すると、図５３の（ａ）と（ｂ）に示すようになる。この場合、Ｃスペアの割当て範囲が重複しているが、それぞれの共用単位は基本形になっていることがわかる。
【０４０９】
さて、上記したように、もとの処理単位が「各スペアは１本のラインとして割当てられる。」という条件を満足せず、基本形になっていない場合であっても、この処理単位を共用単位に分割することにより、各々の共用単位については、これまでに説明してきた救済処理を適用することができるようになる。
【０４１０】
そこで、上記条件を満足していない処理単位については、まず、各共用単位ごとに（他の共用単位を考慮せずに）救済解を求め、そして、共用単位間で共用しているスペア群について考慮しながら各共用単位の救済解を合成することにより、当該処理単位の救済解を生成することができる。
【０４１１】
以下では、このように「各スペアは１本のラインとして割当てられる。」という条件を満足しない処理単位に対する救済処理を行う半導体不良ビット救済処理装置について説明する。なお、以下では、１つの処理単位を対象として説明を行う。
【０４１２】
図５４に、この場合における半導体不良ビット救済処理装置の基本構成例を示す。また、図５５に、この場合における救済処理の手順の一例を示す。
【０４１３】
入力処理部１００１は、対象となる処理単位に固有の情報等を入力し、またメモリーテスタ装置からの処理単位（例えば図５０）に対する不良ビットのアドレス情報（行アドレスと列アドレスの対）を入力する（ステップＳ１００１）。
【０４１４】
なお、処理単位に固有の情報としては、例えば、共用単位の数、共用単位のＲ，Ｃブロック数、共用単位の１ブロック用のＲ，Ｃスペア数、共用単位のＲ，Ｃブロックの列，行サイズなどである。
【０４１５】
次に、入力処理部１００１は、処理単位に固有の情報を参照して、入力された処理単位に対する不良ビットのアドレス情報を、各共用単位（例えば図５１の（ａ）と（ｂ））に対するアドレス情報に変換（分配）する（ステップＳ１００２）。
【０４１６】
例えば、図５０の例の場合にブロックＳ０の不良ビットは図５１（ａ）のように共用単位Ｅ１に割り振り、ブロックＳ１の不良ビットは図５１（ｂ）のように共用単位Ｅ２に割り振る。メインの他のブロックやＣスペアについても同様である。Ｒスペアとリンボの不良ビットについては全ての共用単位に共通に割り振る。
【０４１７】
次に、共用単位救済処理部１００２は、共用単位ごとに、救済処理を行って、救済解を求める（ステップＳ１００３）。この救済処理には、例えば、第１の実施形態として説明したものやその変形例などを用いることができる。
【０４１８】
ここで求める救済解は、各共用単位における救済すべき不良ラインと使用不可のスペアとを示す情報とする（スペアが必要な不良ラインのアドレスに、実際のスペアのアドレスを割当てることはしない）。
【０４１９】
ここでは、各共用単位についてそれぞれ、複数の救済解を求めるものとする（上限の個数を決めておくものとする）。
【０４２０】
以下では、各共用単位で求められた救済解を、解候補と呼ぶ。なお、複数の救済解を求める方法としては、例えば、第１の実施形態におけるＳ６０２とＳ６０３を繰返し行うなど、種々の方法が考えられる。
【０４２１】
なお、この各共用単位に対する救済処理は、並列に実行してもよいし、順次実行してもよい。
【０４２２】
また、１つでも救済不可となった共用単位が存在する場合には、当該処理単位は救済不可となる。
【０４２３】
次に、解候補合成処理部１００３は、各共用単位から１つずつ選出した解候補を、共用単位間で共用しているスペア群について考慮しながら合成して、当該処理単位の救済解を生成する（ステップＳ１００４）。なお、この共用単位の解候補の合成処理については後で詳しく説明する。
【０４２４】
次に、出力処理部１００４は、当該処理単位の救済解が存在する場合には、当該救済解についてアドレスを変換し直したものを出力し、救済解が存在しない場合には、その旨を示すメッセージ等を出力する（ステップＳ１００５）。
【０４２５】
なお、出力する救済解は、当該処理単位における救済すべき不良ラインとその救済に使用可能のスペアとを示す情報としてもよいし、どのスペアでどの不良ラインを救済するかを特定した情報としてもよい。
【０４２６】
また、ラインフェイル処理を行う場合には、例えば、第１の実施形態と同様に入力された処理単位の不良ビットのアドレスデータに対してラインフェイル処理（図１５のステップＳ２０１）を行い、ステップＳ１００３において共用単位毎にラインフェイル処理（図１５のステップＳ２０２）を行う。
【０４２７】
以下では、各共用単位から１つずつ選出した解候補の合成方法として、幾つかの方法について説明する。解候補の合成では、複数の共用単位で共用されているスペアをいかに扱うかがポイントとなる。なお、選出のしかたや最適解の探索などについては後述する。
【０４２８】
解候補の合成方法の第１の例について説明する。
【０４２９】
本例では、Ｒスペアが共用単位間で共用されるので、Ｒスペアに関して処理を適用することになる。
【０４３０】
まず、各共用単位から解候補を１つずつ選出する。
【０４３１】
次に、選出された解候補それぞれにおいて使用不可となったＲスペアの和集合（共用単位の解候補のうちの少なくとも１つにおいて使用不可となったＲスペアの集合）を求め、Ｒブロック毎に「Ｒスペアの総数」から「使用不可となったＲスペア数」を減じて「Ｒスペアの残数」を求める。また、選出された解候補において「Ｒスペアが必要な不良ラインの総数」を求める。
【０４３２】
例えば、共用単位が２つあり、左側のＲスペアを第１番〜第４番とし（総数を４本とし）、第１の共用単位では１番のＲスペアが使用不可能となり、第２の共用単位では２番のＲスペアが使用不可となった場合には、左側の使用不可のＲスペアの和集合は１番と２番のＲスペア（すなわち２本）であり、左側の使用可能なＲスペアの残数は４−２＝２本となる。
【０４３３】
また、例えば、共用単位が２つあり、左側のＲスペアを第１番〜第４番とし（総数を４本とし）、第１の共用単位では１番と３番のＲスペアが使用不可となり、第２の共用単位では２番と３番のＲスペアが使用不可となった場合には、左側の使用不可のＲスペアの和集合は１番と２番と３番のＲスペア（すなわち３本）であり、左側の使用可能なＲスペアの残数は４−３＝１本となる。
【０４３４】
次に、各Ｒブロック毎に、「Ｒスペアの残数」と「Ｒスペアが必要な不良ラインの総数」とを比較して、「Ｒスペアの残数」の方が大きいかまたは等しければ、当該解候補の組合わせに対して合成解が存在すると判定する。一方、１つでも「Ｒスペアの残数」の方が小さいＲブロックがあれば、当該解候補の組合わせに対して合成解が存在しないと判定する。
【０４３５】
なお、合成解が存在すると判定された解候補の組合わせから当該処理単位の救済解（広い意味での解）を生成するにあたっては、共用単位間で共用されているＲスペアについては、処理対象とした全Ｒスペアから上記の使用不可のＲスペアの和集合に属するものを除外したＲスペアと、Ｒスペアが必要な不良ラインとを示す情報が解となる。
【０４３６】
共用単位間で共用されていないＣスペアについては各共用単位の解候補の内容をそのまま用いることができる。
【０４３７】
また、出力する救済解として、どのスペアでどの不良ラインを救済するかを特定した情報を出力する場合には、処理単位レベルでのスペア割当てを行えばよい。
【０４３８】
次に、解候補の合成方法の第２の例について説明する。
【０４３９】
不使用スペアは共用単位に依存するものなので、ある共用単位で不使用としたスペアであっても、他の共用単位では不使用としていないスペアも存在し得る。上記の第１の例に係る合成方法は処理が速いのが利点であるが、合成解があるのにそれが求まらない場合もあり得る。
【０４４０】
そこで、本例では、各共用単位毎に順番にスペアの割当てを行って行く。
【０４４１】
まず、各共用単位から解候補を１つずつ選出する。
【０４４２】
次に、第１の共用単位について、当該共用単位において使用不可となったＲスペア以外のＲスペアを用いて、不良ラインを救済する。
【０４４３】
次に、第２の共用単位について、当該共用単位において使用不可となったＲスペアおよび第１の共用単位の救済で使用されたＲスペアを使用不可として、それ以外のＲスペアを用いて、不良ラインを救済する。
【０４４４】
共用単位が３つ以上ある場合には、以下同様にして、前回までの共用単位で使用したＲスペアと当該共用単位で使用不可となったＲスペアを当該共用単位における使用不可のＲスペアとして、不良ラインを救済する。
【０４４５】
なお、不良ラインが存在しない共用単位については、上記処理を行う必要はない。
【０４４６】
例えば、左側のＲスペアについてのみ説明すると、共用単位が２つあり、左側のＲスペアを第１番〜第４番とし（総数を４本とし）、第１の共用単位では１番のＲスペアが使用不可となり、Ｒスペアで救済すべきラインが１本であった場合には、第１番以外のＲスペアを使用することとなる。ここでは、第２番のＲスペアを使用したものとする。次に、第２の共用単位では３番のＲスペアが使用不可となり、Ｒスペアで救済すべきラインが２本であった場合には、この３番のＲスペアおよび第１の共用単位で使用済みの第２番のＲスペア以外のＲスペアを使用することとなる。ここでは、第１番と第４番のＲスペアを使用したものとする。この結果、左側のＲスペアについて、合成解が得られたことになる。右側のＲスペアについても同様にして処理が行われる。
【０４４７】
なお、スペアの使用方法に制約があり、共用単位の解候補を求めるまでの段階でこの制約を考慮していない場合には、例えば上記の解候補の合成において、処理単位の救済解がこの制限を満足するか否かをもチェックするものとする。
【０４４８】
さて、上記では、解候補の１つの組合わせに対する合成処理について説明したが、以下では、複数の組合わせのなかから１つを選択する手順について説明する。
【０４４９】
図５６に解候補の合成処理の手順の一例を示す。
【０４５０】
この手順は、処理単位の救済解が１つ得られた時点でその組合わせを採用するもので、共用単位の各々から解候補を１つずつ選出し（ステップＳ１０１１）、この解候補を上記したような処理によって合成して当該処理単位の救済解が得られるか否かを判定し（ステップＳ１０１２）、得られた場合には（ステップＳ１０１３）、その救済解を採用することとして、処理を終了し、得られなかった場合には（ステップＳ１０１３）、次の組合わせを選出して同様の処理を行う（ステップＳ１０１４，Ｓ１０１１，Ｓ１０１２）。規定数の組合わせ（全ての組合わせ数あるいはそれより少ない所定数）について当該処理単位の救済解が得られなかった場合には（ステップＳ１０１４）、救済不可とする。
【０４５１】
各共用単位からの解候補の選出方法としては、例えば、ランダムに選出する方法、各共用単位について救済に使用するＣスペアの多いものをなるべく優先的に選出する方法など、種々の方法が考えられる。
【０４５２】
次に、図５７、解候補の合成処理の手順の他の例を示す。
【０４５３】
この手順は、処理単位の救済解として最適なものを与える組合わせを全部または一部の組合わせのなかから探索するもので、共用単位の各々から解候補を１つずつ選出し（ステップＳ１０２１）、この解候補を上記したような処理によって合成して当該処理単位の救済解の候補を求めもしくは救済不可を判断する（ステップＳ１０２２）、という一連を処理を、解候補の組合わせを変えながら、規定数の組合わせ（全ての組合わせ数あるいはそれより少ない所定数）について行う（ステップＳ１０２１，Ｓ１０２２，Ｓ１０２３）。そして、当該処理単位の救済解となり得る候補が１つ得られた場合には（ステップＳ１０２４）、これを救済解として採用する（ステップＳ１０２５）。当該処理単位の救済解となり得る候補が２以上得られた場合には（ステップＳ１０２４）、救済に使用するスペアが最も少なくて済む候補を最良の救済解として採用する（ステップＳ１０２６）。救済に使用するスペアが最も少なくて済む候補が複数ある場合には、他の選択基準を用いてあるいはランダムに、いずれか１つを選択する。当該処理単位の救済解となり得る候補が１つも得られなかった場合には（ステップＳ１０２４）、当該処理単位は救済不可となる。
【０４５４】
各共用単位からの解候補の選出方法としては、例えば、ｍ個の共用単位の解候補をｎ個ずつ求め、ｎｍ  種類の組合わせを全て選択する方法、ｍ個の共用単位の解候補をｎ個ずつ求め、ｎｍ  より小さい種類数の組合わせをランダムに選択する方法、ｍ個の共用単位の解候補をｎ個ずつ求め、各共用候補の解候補について救済に使用するＣスペアの多い順に取り出したｋ個（ｋ＜ｎ）の部分について、ｋｍ  種類数の全ての組合わせを選択する方法など、種々の方法が考えられる。
【０４５５】
なお、当該処理単位の救済解として複数のものを出力し、例えばリペア装置側で実際に使用する１つを選択するようにしてもよい。
【０４５６】
以上では、Ｃスペアを細分化して割当てることができる例、すなわちＲスペアを共用単位間で共用する例をもとに説明したが、Ｒスペアを細分化して割当てることができる例、すなわちＲスペアを共用単位間で共用する例に対しても同様である（上記の説明において、ＣスペアとＲスペアを逆にすればよい）。
【０４５７】
また、ＣスペアおよびＲスペアのいずれも細分化して割当てることができる場合についても、本手法は同様に適用することができる。
【０４５８】
例えば、図５８に例示するメモリーブロックとスペアとリンボの構成は、図５０のＣスペアの構造をＲスペアにも適用したもので、ＲスペアおよびＣスペアを細分化して割当てることができるデバイスの処理単位の例である。すなわち、ＲスペアおよびＣスペアのいずれも上記した「各スペアは１本のラインとして割当てられる。」という条件を満足していない場合である。
【０４５９】
図５８の例においては、Ｓ０〜Ｓ１５の１６個のブロックからなるメインを囲むように、左右４本ずつのＲスペアと上下４本ずつのＣスペアと必要なリンボが配置されている（実際に図５８のような構成になっていてもよいし、アドレス変換後の配置が図５８のようであってもよい）。
【０４６０】
左側の４本のＲスペアはＢＬＫ−１用であり、右側の４本のＲスペアはＢＬＫ−２用であるものとする。また、上側の３本のＣスペアはＢＬＫ−Ａ用であり、下側の４本の３スペアはＢＬＫ−Ｂ用であるものとする。
【０４６１】
なお、左右のそれぞれのＲスペアについて、Ｓ０，Ｓ１，Ｓ２，Ｓ３に対応する部分をｒ１、Ｓ４，Ｓ５，Ｓ６，Ｓ７に対応する部分をｒ２、Ｓ８，Ｓ９，Ｓ１０，Ｓ１１に対応する部分をｒ３、Ｓ１２，Ｓ１３，Ｓ１４，Ｓ１５に対応する部分をｒ４とし、上下のそれぞれのＣスペアについて、Ｓ０，Ｓ４，Ｓ８，Ｓ１２に対応する部分をｃ１、Ｓ１，Ｓ５，Ｓ９，Ｓ１３に対応する部分をｃ２、Ｓ２，Ｓ６，Ｓ１０，Ｓ１４に対応する部分をｃ３、Ｓ３，Ｓ７，Ｓ１１，Ｓ１５に対応する部分をｃ４と呼ぶものとする。
【０４６２】
ＲスペアおよびＣスペアについては、実際の割当てにおいては、１本のスペアを４当分して、その一部だけを使うことが可能であるものとする。また、ここでは、それら細分化された４本の短いスペアには、他の短いスペアと連動して用いなければならないという制約があるものとする。例えば、｛ｒ１，ｒ２，ｒ３，ｒ４｝をそれら４本の短いＲスペアとしたとき、｛ｒ１，ｒ３｝，｛ｒ２，ｒ４｝は、それぞれメインの同一の列アドレスを救済しなければならないという制約と、｛ｃ１，ｃ２，ｃ３，ｃ４｝をそれら４本の短いＣスペアとしたとき、｛ｃ１，ｃ３｝，｛ｃ２，ｃ４｝は、それぞれメインの同一の行アドレスを救済しなければならないという制約である。つまり、短いスペアは１つおきに２本ずつ１本にまとめた状態で使用しなければならないという制約である（実質的には１本のスペアを２当分して、その一部だけを使うことが可能であるということになる）。
【０４６３】
このような場合には、図５０の例と同様に、上記の連動という性質を用いてメインとＲスペアおよびＣスペアを縦横方向に４分割し、図５９の（ａ）〜（ｄ）のような４つの共用単位に分けて扱うことにする。この場合、図６０に示すように、共用単位Ｅ１とＥ２の間ではｒ１とｒ３の短いスペアが共用され、共用単位Ｅ３とＥ４の間ではｒ２とｒ４の短いスペアが共用され、共用単位Ｅ１とＥ３の間ではｃ１とｃ３の短いスペアが共用され、共用単位Ｅ２とＥ４の間ではｃ２とｃ４の短いスペアが共用されることになる。
【０４６４】
このように分割した場合、４つの各共用単位それぞれにおいてはスペアが１本のラインとしてメインのラインを救済するという対応関係が付けられているため、上記条件を満足し、４つの共用単位はいずれも基本形になっていることがわかる。
【０４６５】
したがって、このようにＲスペアおよびＣスペアの両方が上記条件を満足しない場合であっても、処理単位を共用単位に分割し、各共用単位毎に解候補を求め、それらを合成することによって、当該処理単位に対する救済解を得ることができる。
【０４６６】
ただし、この場合、図６０に例示するように、ＲスペアおよびＣスペアの両方が複数の共用単位で共用されているので、解候補の合成処理にあたっては、ＲスペアとＣスペアのそれぞれについて、前述したような解候補の合成を行えばよい。
【０４６７】
なお、本実施形態では、１つの半導体デバイスの１チップ内の１つのメモリーブロックに対する処理を中心に説明を行ったが、前述したような、１チップ単位の処理、１ウエハ単位の処理、１ロット単位の処理に関連して説明した構成、システム構成、本半導体不良ビット救済処理装置をソフトウエアで実現する構成などの種々の構成は、本実施形態にも適用可能である。
【０４６８】
本発明は、上述した実施の形態に限定されるものではなく、その技術的範囲において種々変形して実施することができる。
【０４６９】
【発明の効果】
本発明によれば、メモリー部分を有する半導体デバイスにおいて予備ラインに不良ビットセルが検出されている場合であっても、救済の可／不可と、救済が可能な場合に不良ラインと予備ラインとの間の対応関係を高速かつ安定的にまた求めることができる。また、処理に制限時間が設けられている場合でも制限時間内に上記の結果を得ることが期待できる。また、不良ビットセルが一様に散らばって出現するような場合あるいはラインフェイルを救済した後に残った不良の多くが孤立不良のような場合などには、制限時間を超える探索を行うことが極力少なくなり、不良ラインの使用本数を最小本数またはこれに極めて近い本数で実現した不良ラインと予備ラインとの間の対応関係を求めることが多くなると期待できる。
【図面の簡単な説明】
【図１】メモリーブロックとスペアとリンボの構成の一具体例を示す図
【図２】メモリーブロックのみに不良ビットが存在する場合の不良ビットの救済を説明するための図
【図３】スペアやリンボにも不良ビットが存在する場合の不良ビットの救済を説明するための図
【図４】メモリーブロックからなる行列Ａとメモリーブロックとスペアとリンボからなる行列Ｂを説明するための図
【図５】行列Ａの救済解と行列Ｂの救済解との関係を説明するための図
【図６】行列Ａの救済解と行列Ｂの救済解との関係を説明するための他の図
【図７】本発明の実施形態に係る半導体不良ビット救済処理装置の基本構成を示す図
【図８】本発明の実施形態に係る半導体不良ビット救済処理装置の処理手順の一例を示すフローチャート
【図９】行列Ｂの一例を示す図
【図１０】行列Ｂによる救済解の一例を示す図
【図１１】行列Ａにおける救済解の一例を示す図
【図１２】本発明の実施形態に係る半導体不良ビット救済処理装置の処理手順の他の例を示すフローチャート
【図１３】本発明の実施形態に係る半導体不良ビット救済処理装置の処理手順のさらに他の例を示すフローチャート
【図１４】本発明の第１の実施形態に係る半導体不良ビット救済処理装置の概略構成を示す図
【図１５】本発明の第１の実施形態に係る半導体不良ビット救済処理装置の処理手順の一例を示すフローチャート
【図１６】行列Ｂの一例を示す図
【図１７】図１６の行列Ｂに対応する入力データの一例を示す図
【図１８】スペアの残数やＢスペアで救済されるラインの情報の保持方法の一例を示す図
【図１９】図１５のフローチャートにおけるステップＳ１０１およびＳ２０１のより詳しい処理手順の一例を示すフローチャート
【図２０】Ｂスペアにより救済される行列Ｂにおける行や列のラインを示す図
【図２１】入力データ格納用ファイルの形式の一例を示す図
【図２２】ラインフェイル処理後の縮小されたＢ行列を示す図
【図２３】図２２の行列Ｂに対応する２部グラフを示す図
【図２４】図２２の２部グラフにおけるリンク情報を記憶したテーブルの一例を示す図
【図２５】図２３の２部グラフに対する最大マッチングの一例と最小被覆の一例を示す図
【図２６】最大マッチングを記憶したテーブルの一例を示す図
【図２７】ＤＭ分解とその縮約グラフを説明するための図
【図２８】図２３の２部グラフから求めたＤＭ分解を示す図
【図２９】図２８に対するＤＭ分解の縮約グラフを示す図
【図３０】図２８に対するＤＭ分解とその縮約グラフの保持方法の一例を示す図
【図３１】図２８のＤＭ分解をもとにしたスペアの割り当て処理を説明するための図
【図３２】図１５のフローチャートにおけるステップＳ６０２およびＳ６０３のより詳しい処理手順の一例を示すフローチャート
【図３３】Ｂ行列の一例を示す図
【図３４】図３３のＢ行列においてラインフェイルを算出した後の行列Ｂに対するＤＭ分解行列を示す図
【図３５】本発明の第２の実施形態に係る半導体不良ビット救済処理装置の概略構成を示す図
【図３６】本発明の第２の実施形態に係る半導体不良ビット救済処理装置の処理手順の一例を示すフローチャート
【図３７】行列Ｂ、２部グラフおよび接続行列を説明するための図
【図３８】メモリーブロックとスペアとリンボの構成の一具体例を示す図
【図３９】本発明の他の実施形態に係る半導体不良ビット救済処理方法を説明するための図
【図４０】半導体不良ビット救済処理装置に与えられるデータ形式の一例
【図４１】半導体不良ビット救済処理装置のシステム構成例を示す図
【図４２】半導体不良ビット救済処理装置のシステム構成例を示す図
【図４３】半導体不良ビット救済処理装置の装置構成例を示す図
【図４４】本発明の第３の実施形態に係る半導体不良ビット救済処理装置の概略構成を示す図
【図４５】本発明の第３の実施形態に係る半導体不良ビット救済処理装置の処理手順の一例を示すフローチャート
【図４６】同実施形態の適用例を説明するための図
【図４７】同実施形態の適用例を説明するための図
【図４８】メモリーブロックとスペアとリンボの構成の一具体例を示す図
【図４９】基本形となる処理単位を説明するための図
【図５０】基本形でない処理単位を説明するための図
【図５１】基本形となる共用単位を説明するための図
【図５２】基本形でない処理単位を説明するための図
【図５３】基本形となる共用単位を説明するための図
【図５４】本発明の第４の実施形態に係る半導体不良ビット救済処理装置の概略構成を示す図
【図５５】本発明の第４の実施形態に係る半導体不良ビット救済処理装置の処理手順の一例を示すフローチャート
【図５６】同実施形態に係る解候補合成処理の手順の一例を示すフローチャート
【図５７】同実施形態に係る解候補合成処理の手順の他の例を示すフローチャート
【図５８】基本形でない処理単位を説明するための図
【図５９】基本形となる共用単位を説明するための図
【図６０】共用単位で共用されるスペア群を説明するための図
【符号の説明】
１…入力処理部
２…ラインフェイル処理部
３…救済処理部
４…出力処理部
１０…データ入力部
２０…ラインフェイル判定部
３０…２部グラフ作成部
３５…線形計画問題表現部
４０…最大マッチング作成部
４５…２段階単体法適用部
５０…ＤＭ分解作成部
６０…救済解作成部
７０…救済結果出力部
２００…メモリーブロック
２０１〜２０４…サブブロック
２１１〜２１４…スペア
２１５〜２１８…リンボ
３２１…ＣＰＵ
３２２…ＲＡＭ
３２３…ハードディスク装置
３２４…入力装置
３２５…出力装置
３２６…バス
１００，１００−１〜１００−ｎ…第１の救済処理部
２００…第２の救済処理部
３００…解の統合処理部
１００１…入力処理部
１００２…ラインフェイル処理部
１００３…共用単位救済処理部
１００４…解候補合成処理部
１００５…出力処理部
１０１２…ラインフェイル処理部
【図１】
0003581249.tif 000008
【図２】
0003581249.tif 000009
【図３】
0003581249.tif 000010
【図４】
0003581249.tif 000011
【図５】
0003581249.tif 000012
【図６】
0003581249.tif 000013
【図７】
0003581249.tif 000014
【図８】
0003581249.tif 000015
【図９】
0003581249.tif 000016
【図１０】
0003581249.tif 000017
【図１１】
0003581249.tif 000018
【図１２】
0003581249.tif 000019
【図１３】
0003581249.tif 000020
【図１４】
0003581249.tif 000021
【図１５】
0003581249.tif 000022
【図１６】
0003581249.tif 000023
【図１７】
0003581249.tif 000024
【図１８】
0003581249.tif 000025
【図１９】
0003581249.tif 000026
【図２０】
0003581249.tif 000027
【図２１】
0003581249.tif 000028
【図２２】
0003581249.tif 000029
【図２３】
0003581249.tif 000030
【図２４】
0003581249.tif 000031
【図２５】
0003581249.tif 000032
【図２６】
0003581249.tif 000033
【図２７】
0003581249.tif 000034
【図２８】
0003581249.tif 000035
【図２９】
0003581249.tif 000036
【図３０】
0003581249.tif 000037
【図３１】
0003581249.tif 000038
【図３２】
0003581249.tif 000039
【図３３】
0003581249.tif 000040
【図３４】
0003581249.tif 000041
【図３５】
0003581249.tif 000042
【図３６】
0003581249.tif 000043
【図３７】
0003581249.tif 000044
【図３８】
0003581249.tif 000045
【図３９】
0003581249.tif 000046
【図４０】
0003581249.tif 000047
【図４１】
0003581249.tif 000048
【図４２】
0003581249.tif 000049
【図４３】
0003581249.tif 000050
【図４４】
0003581249.tif 000051
【図４５】
0003581249.tif 000052
【図４６】
0003581249.tif 000053
【図４７】
0003581249.tif 000054
【図４８】
0003581249.tif 000055
【図４９】
0003581249.tif 000056
【図５０】
0003581249.tif 000057
【図５１】
0003581249.tif 000058
【図５２】
0003581249.tif 000059
【図５３】
0003581249.tif 000060
【図５４】
0003581249.tif 000061
【図５５】
0003581249.tif 000062
【図５６】
0003581249.tif 000063
【図５７】
0003581249.tif 000064
【図５８】
0003581249.tif 000065
【図５９】
0003581249.tif 000066
【図６０】
0003581249.tif 000067