(57)【要約】  複数の予備ラインが設けられたメモリについて、いずれのフェイルラインに予備ラインを割り当てるかを決定する予備ライン割当装置であって、それぞれのフェイルラインに含まれるそれぞれのフェイルビットについて、当該フェイルビットを含み、且つ当該フェイルラインとは異なる方向のフェイルラインが有するフェイルビットの個数を直交フェイルビット数として計数して、フェイルビットごとに直交フェイルビット数を格納するビット計数部と、それぞれのフェイルラインに含まれるフェイルビットの直交フェイルビット数に基づいて、それぞれのフェイルラインの重み係数を算出して、フェイルラインごとに重み係数を格納する重み算出部と、重み算出部が算出した、重み係数の大小関係に基づいて、いずれのフェイルラインに予備ラインを割り当てるかを決定する割当部とを備える予備ライン割当装置を提供する。
2009013832.tif 000002
【特許請求の範囲】
【請求項１】
複数の予備ラインが設けられたメモリについて、フェイルビットを有する行方向のフェイルライン及び列方向のフェイルラインのうち、いずれの前記フェイルラインに前記予備ラインを割り当てるかを決定する予備ライン割当装置であって、
それぞれの前記フェイルラインに含まれるそれぞれのフェイルビットについて、当該フェイルビットを含み、且つ当該フェイルラインとは異なる方向のフェイルラインが有するフェイルビットの個数を直交フェイルビット数として計数して、前記フェイルビットごとに前記直交フェイルビット数を格納するビット計数部と、
それぞれの前記フェイルラインに含まれる前記フェイルビットの前記直交フェイルビット数に基づいて、それぞれの前記フェイルラインの重み係数を算出して、前記フェイルラインごとに前記重み係数を格納する重み算出部と、
前記重み算出部が算出した、前記重み係数の大小関係に基づいて、いずれの前記フェイルラインに前記予備ラインを割り当てるかを決定する割当部と
を備える予備ライン割当装置。
【請求項２】
前記ビット計数部は、それぞれの前記フェイルビットについて、行方向のフェイルラインおよび列方向のフェイルラインの双方に対して、前記直交フェイルビット数を計数する
請求項１に記載の予備ライン割当装置。
【請求項３】
前記重み算出部は、それぞれの前記フェイルラインが有する前記フェイルビットの、当該フェイルラインにおける前記直交フェイルビット数の逆数の総和に基づいて、当該フェイルラインの前記重み係数を算出する
請求項２に記載の予備ライン割当装置。
【請求項４】
前記割当部は、前記重み係数に基づいて、いずれかの前記フェイルラインに前記予備ラインを割当てて、
前記重み算出部は、前記予備ラインが割り当てられた前記フェイルラインに含まれる前記フェイルビットを除外した場合のそれぞれの前記フェイルラインの前記重み係数を算出して、前記フェイルラインごとに前記重み係数を新たに格納し、
前記割当部は、前記重み算出部が新たに格納した前記重み係数に基づいて、次に前記予備ラインを割り当てるべき前記フェイルラインを選択する
請求項２に記載の予備ライン割当装置。
【請求項５】
前記割当部は、前記重み係数が最も大きい前記フェイルラインに対して前記予備ラインを順次割り当て、
前記予備ライン割当装置は、前記重み係数が最も大きい前記フェイルラインに対して前記予備ラインを順次割り当てた場合に、全ての前記フェイルビットを救済できるか否かを判定する救済可否判定部を更に備え、
前記割当部は、前記救済可否判定部が、いずれかの前記フェイルビットを救済できないと判定した場合に、前記予備ラインが既に割り当てられている前記フェイルラインのいずれかを第１の前記フェイルラインとして、前記第１のフェイルラインに対する前記予備ラインの割り当てを解除し、前記第１のフェイルラインが有する前記フェイルビットを含み、且つ前記第１のフェイルラインとは異なる方向の、それぞれの第２の前記フェイルラインを選択して前記予備ラインを割り当てる
請求項４に記載の予備ライン割当装置。
【請求項６】
前記重み算出部は、前記救済可否判定部が、いずれかの前記フェイルビットを救済できないと判定した場合に、前記第１のフェイルラインに前記予備ラインを割当てる前の前記重み係数を再計算する
請求項５に記載の予備ライン割当装置。
【請求項７】
前記救済可否判定部は、前記割当部が一つの前記予備ラインを前記フェイルラインに割り当てるごとに、予め定められた判定基準に基づいて、全ての前記フェイルビットを救済できる可能性が残っているか否かを判定し、
前記割当部は、前記救済可否判定部において全ての前記フェイルビットを救済できる可能性が無いと判定された場合に、直前に前記予備ラインを割り当てた前記フェイルラインを前記第１のフェイルラインとして前記予備ラインの割り当てを解除する
請求項６に記載の予備ライン割当装置。
【請求項８】
前記救済可否判定部は、前記割当部が一つの前記予備ラインを前記フェイルラインに割り当てるごとに、予め定められた判定基準に基づいて、全ての前記フェイルビットを救済できる可能性が残っているか否かを判定し、
前記割当部は、前記救済可否判定部において全ての前記フェイルビットを救済できる可能性が無いと判定された場合に、最初に前記予備ラインを割り当てた前記フェイルラインを前記第１のフェイルラインとして前記予備ラインの割り当てを解除する
請求項６に記載の予備ライン割当装置。
【請求項９】
前記メモリの記憶領域は、列方向及び行方向の少なくとも一方において、複数の記憶ブロックに分割され、前記メモリは、それぞれの記憶ブロック毎の予備ラインを有し、
前記割当部は、前記救済可否判定部が、いずれかの前記フェイルビットを救済できないと判定した場合に、前記第１のフェイルラインと同一の方向の前記フェイルラインであり、且つ記憶ブロック毎の前記フェイルビット数が、前記第１のフェイルラインと同一の前記フェイルラインに、前記予備ラインを更に割り当てる
請求項５に記載の予備ライン割当装置。
【請求項１０】
前記割当部は、予め定められた数の前記フェイルビットがある前記フェイルラインに、前記予備ラインを予め割り当てる
請求項１に記載の予備ライン割当装置。
【請求項１１】
当該フェイルビットを含む列方向及び行方向の前記フェイルラインに、他の前記フェイルビットが無い場合に、当該フェイルビットを孤立フェイルビットとして検出する孤立フェイル検出部を更に備え、
前記割当部は、
前記孤立フェイルビットの個数から前記フェイルラインに割当てられていない列方向の前記予備ラインの本数を減じ、減算結果に応じた本数の行方向の前記予備ラインを、前記孤立フェイルビットを含む前記フェイルラインに割り当て、
前記孤立フェイルビットの個数から前記フェイルラインに割当てられていない行方向の前記予備ラインの本数を減じ、減算結果に応じた本数の列方向の前記予備ラインを、前記孤立フェイルビットを含む前記フェイルラインに割り当てる
請求項１に記載の予備ライン割当装置。
【請求項１２】
前記孤立フェイル検出部は、前記割当部が前記予備ラインを前記フェイルラインに割当てる毎に、当該フェイルラインに含まれる前記フェイルビットを除外した状態における、前記孤立フェイルビットを検出する
請求項１１に記載の予備ライン割当装置。
【請求項１３】
前記割当部は、前記予備ラインが割当てられていない全ての前記フェイルビットが、前記孤立フェイルビットである場合に、予め定められた方向の前記予備ラインを優先して、当該フェイルラインに割当てる
請求項１１に記載の予備ライン割当装置。
【請求項１４】
前記救済可否判定部は、
それぞれの前記記憶ブロックにおける、列方向の前記フェイルラインに含まれる前記フェイルビットの個数の最大値と、当該記憶ブロックに属する列方向の前記予備ラインのうち、前記フェイルラインに割当てられてない前記予備ラインの本数とを乗算した第１の乗算値を算出する第１の乗算部と、
それぞれの前記記憶ブロックにおける、行方向の前記フェイルラインに含まれる前記フェイルビットの個数の最大値と、当該記憶ブロックに属する行方向の前記予備ラインのうち、前記フェイルラインに割当てられてない前記予備ラインの本数とを乗算した第２の乗算値を算出する第２の乗算部と、
それぞれの前記記憶ブロックについて、前記第１の乗算値及び前記第２の乗算値の和が、当該記憶ブロックに含まれる前記フェイルビットの総数より小さいか否かを判定し、いずれかの前記記憶ブロックに対して、前記乗算値の和が前記フェイルビットの総数より小さいと判定した場合に、全ての前記フェイルビットを救済できないと判定する比較部と
を有する請求項９に記載の予備ライン割当装置。
【請求項１５】
複数の予備ラインが設けられたメモリのフェイルビットを救済するメモリ救済装置であって、
前記メモリにおいて、前記フェイルビットを有する行方向のフェイルライン及び列方向のフェイルラインのうち、いずれの前記フェイルラインに前記予備ラインを割り当てるかを決定する予備ライン割当装置と、
前記予備ライン割当装置が決定した割当てを、前記メモリに設定する設定部と
を備え、
前記予備ライン割当装置は、
それぞれの前記フェイルラインに含まれるそれぞれのフェイルビットについて、当該フェイルビットを含み、且つ当該フェイルラインとは異なる方向のフェイルラインが有するフェイルビットの個数を直交フェイルビット数として計数して、前記フェイルビットごとに前記直交フェイルビット数を格納するビット計数部と、
それぞれの前記フェイルラインに含まれる前記フェイルビットの前記直交フェイルビット数に基づいて、それぞれの前記フェイルラインの重み係数を算出して、前記フェイルラインごとに前記重み係数を格納する重み算出部と、
前記重み算出部が算出した、前記重み係数の大小関係に基づいて、いずれの前記フェイルラインに前記予備ラインを割り当てるかを決定する割当部と
を有するメモリ救済装置。
【請求項１６】
複数の予備ラインが設けられたメモリについて、フェイルビットを有する行方向のフェイルライン及び列方向のフェイルラインのうち、いずれの前記フェイルラインに前記予備ラインを割り当てるかを決定する予備ライン割当方法であって、
それぞれの前記フェイルラインに含まれるそれぞれのフェイルビットについて、当該フェイルビットを含み、且つ当該フェイルラインとは異なる方向のフェイルラインが有するフェイルビットの個数を直交フェイルビット数として計数して、前記フェイルビットごとに前記直交フェイルビット数を記憶し、
それぞれの前記フェイルラインに含まれる前記フェイルビットの前記直交フェイルビット数に基づいて、それぞれの前記フェイルラインの重み係数を算出して、前記フェイルラインごとに前記重み係数を記憶し、
前記重み係数の大小関係に基づいて、いずれの前記フェイルラインに前記予備ラインを割り当てるかを決定する予備ライン割当方法。
【請求項１７】
メモリを製造するメモリ製造方法であって、
複数の予備ラインが設けられたメモリを形成する段階と、
形成した前記メモリにおいて、フェイルビットを有する行方向のフェイルライン及び列方向のフェイルラインのうち、いずれの前記フェイルラインに前記予備ラインを割り当てるかを決定することにより、前記メモリを救済する段階と
を備え、
前記メモリを救済する段階は、
それぞれの前記フェイルラインに含まれるそれぞれのフェイルビットについて、当該フェイルビットを含み、且つ当該フェイルラインとは異なる方向のフェイルラインが有するフェイルビットの個数を直交フェイルビット数として計数して、前記フェイルビットごとに前記直交フェイルビット数を記憶し、
それぞれの前記フェイルラインに含まれる前記フェイルビットの前記直交フェイルビット数に基づいて、それぞれの前記フェイルラインの重み係数を算出して、前記フェイルラインごとに前記重み係数を記憶し、
前記重み係数の大小関係に基づいて、いずれの前記フェイルラインに前記予備ラインを割り当てるかを決定するメモリ製造方法。
【請求項１８】
コンピュータを、複数の予備ラインが設けられたメモリについて、フェイルビットを有する行方向のフェイルライン及び列方向のフェイルラインのうち、いずれの前記フェイルラインに前記予備ラインを割り当てるかを決定する予備ライン割当装置として機能させるプログラムであって、
前記コンピュータを、
それぞれの前記フェイルラインに含まれるそれぞれのフェイルビットについて、当該フェイルビットを含み、且つ当該フェイルラインとは異なる方向のフェイルラインが有するフェイルビットの個数を直交フェイルビット数として計数して、前記フェイルビットごとに前記直交フェイルビット数を格納するビット計数部と、
それぞれの前記フェイルラインに含まれる前記フェイルビットの前記直交フェイルビット数に基づいて、それぞれの前記フェイルラインの重み係数を算出して、前記フェイルラインごとに前記重み係数を格納する重み算出部と、
前記重み算出部が算出した、前記重み係数の大小関係に基づいて、いずれの前記フェイルラインに前記予備ラインを割り当てるかを決定する割当部と
して機能させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、予備ライン割当装置、メモリ救済装置、予備ライン割当方法、メモリ製造方法、およびプログラムに関する。本発明は特に、複数の予備ラインが設けられる半導体メモリ等のメモリについて、いずれのフェイルラインに予備ラインを割り当てるかを決定する予備ライン割当装置に関する。
【背景技術】
【０００２】
従来、２次元のマトリクス状に記憶セルが配置された半導体メモリが知られている。半導体メモリの製造においては、全ての記憶セルが正常に動作するように形成することが望ましい。しかし、近年の半導体メモリは非常に多くの記憶セルを有するので、全ての記憶セルを正常に形成することは困難である。【０００３】
これに対し、記憶セルのマトリクスにおける行方向または列方向のアドレスラインに対して、所定の数の予備ラインを予め形成した半導体メモリが知られている。係る半導体メモリにおいて、不良の記憶セル（フェイルビット）を有するアドレスラインを予備ラインで置き換えることにより、不良の記憶セルを有する半導体メモリを救済することができる（例えば、特許文献１参照）。
【特許文献１】特開平２−２４８９９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかし、半導体メモリに形成できる予備ラインの本数は限界がある。このため、フェイルビットを有するアドレスラインに対して、適切に予備ラインを割り当てなければ、全てのフェイルビットを救済することができない場合がある。しかし、近年の半導体メモリは、非常に多くのアドレスラインを有しているので、全てのフェイルビットを救済できるような予備ラインの割り当て解を検出するのに非常に長い時間がかかってしまう。このため、全てのフェイルビットを救済できる予備ラインの割り当て解を、効率よく検出する方法が望まれている。【０００５】
このため本発明は、上述した課題を解決することのできる予備ライン割当装置、メモリ救済装置、予備ライン割当方法、メモリ製造方法、およびプログラムを提供することを目的とする。この目的は、請求の範囲における独立項に記載の特徴の組み合わせにより達成される。また従属項は本発明の更なる有利な具体例を規定する。
【課題を解決するための手段】
【０００６】
上記課題を解決するために本発明の第１の形態においては、複数の予備ラインが設けられたメモリについて、フェイルビットを有する行方向のフェイルライン及び列方向のフェイルラインのうち、いずれのフェイルラインに予備ラインを割り当てるかを決定する予備ライン割当装置であって、それぞれのフェイルラインに含まれるそれぞれのフェイルビットについて、当該フェイルビットを含み、且つ当該フェイルラインとは異なる方向のフェイルラインが有するフェイルビットの個数を直交フェイルビット数として計数して、フェイルビットごとに直交フェイルビット数を格納するビット計数部と、それぞれのフェイルラインに含まれるフェイルビットの直交フェイルビット数に基づいて、それぞれのフェイルラインの重み係数を算出して、フェイルラインごとに重み係数を格納する重み算出部と、重み算出部が算出した、重み係数の大小関係に基づいて、いずれのフェイルラインに予備ラインを割り当てるかを決定する割当部とを備える予備ライン割当装置を提供する。【０００７】
本発明の第２の形態においては、複数の予備ラインが設けられたメモリのフェイルビットを救済するメモリ救済装置であって、メモリにおいて、フェイルビットを有する行方向のフェイルライン及び列方向のフェイルラインのうち、いずれのフェイルラインに予備ラインを割り当てるかを決定する予備ライン割当装置と、予備ライン割当装置が決定した割当てを、メモリに設定する設定部とを備え、予備ライン割当装置は、それぞれのフェイルラインに含まれるそれぞれのフェイルビットについて、当該フェイルビットを含み、且つ当該フェイルラインとは異なる方向のフェイルラインが有するフェイルビットの個数を直交フェイルビット数として計数して、フェイルビットごとに直交フェイルビット数を格納するビット計数部と、それぞれのフェイルラインに含まれるフェイルビットの直交フェイルビット数に基づいて、それぞれのフェイルラインの重み係数を算出して、フェイルラインごとに重み係数を格納する重み算出部と、重み算出部が算出した、重み係数の大小関係に基づいて、いずれのフェイルラインに予備ラインを割り当てるかを決定する割当部とを有するメモリ救済装置を提供する。【０００８】
本発明の第３の形態においては、複数の予備ラインが設けられたメモリについて、フェイルビットを有する行方向のフェイルライン及び列方向のフェイルラインのうち、いずれのフェイルラインに予備ラインを割り当てるかを決定する予備ライン割当方法であって、それぞれのフェイルラインに含まれるそれぞれのフェイルビットについて、当該フェイルビットを含み、且つ当該フェイルラインとは異なる方向のフェイルラインが有するフェイルビットの個数を直交フェイルビット数として計数して、フェイルビットごとに直交フェイルビット数を記憶し、それぞれのフェイルラインに含まれるフェイルビットの直交フェイルビット数に基づいて、それぞれのフェイルラインの重み係数を算出して、フェイルラインごとに重み係数を記憶し、重み係数の大小関係に基づいて、いずれのフェイルラインに予備ラインを割り当てるかを決定する予備ライン割当方法を提供する。【０００９】
本発明の第４の形態においては、メモリを製造するメモリ製造方法であって、複数の予備ラインが設けられたメモリを形成する段階と、形成したメモリにおいて、フェイルビットを有する行方向のフェイルライン及び列方向のフェイルラインのうち、いずれのフェイルラインに予備ラインを割り当てるかを決定することにより、メモリを救済する段階とを備え、メモリを救済する段階は、それぞれのフェイルラインに含まれるそれぞれのフェイルビットについて、当該フェイルビットを含み、且つ当該フェイルラインとは異なる方向のフェイルラインが有するフェイルビットの個数を直交フェイルビット数として計数して、フェイルビットごとに直交フェイルビット数を記憶し、それぞれのフェイルラインに含まれるフェイルビットの直交フェイルビット数に基づいて、それぞれのフェイルラインの重み係数を算出して、フェイルラインごとに重み係数を記憶し、重み係数の大小関係に基づいて、いずれのフェイルラインに予備ラインを割り当てるかを決定するメモリ製造方法を提供する。【００１０】
コンピュータを、複数の予備ラインが設けられたメモリについて、フェイルビットを有する行方向のフェイルライン及び列方向のフェイルラインのうち、いずれのフェイルラインに予備ラインを割り当てるかを決定する予備ライン割当装置として機能させるプログラムであって、コンピュータを、それぞれのフェイルラインに含まれるそれぞれのフェイルビットについて、当該フェイルビットを含み、且つ当該フェイルラインとは異なる方向のフェイルラインが有するフェイルビットの個数を直交フェイルビット数として計数して、フェイルビットごとに直交フェイルビット数を格納するビット計数部と、それぞれのフェイルラインに含まれるフェイルビットの直交フェイルビット数に基づいて、それぞれのフェイルラインの重み係数を算出して、フェイルラインごとに重み係数を格納する重み算出部と、重み算出部が算出した、重み係数の大小関係に基づいて、いずれのフェイルラインに予備ラインを割り当てるかを決定する割当部として機能させるプログラムを提供する。【００１１】
なお上記の発明の概要は、本発明の必要な特徴の全てを列挙したものではなく、これらの特徴群のサブコンビネーションも又発明となりうる。
【図面の簡単な説明】
【００１２】
【図１】半導体メモリ等のメモリ４０を試験するメモリ試験装置１０、およびメモリ４０のフェイルビットを救済するメモリ救済装置２０の一例を示す図である。
【図２】予備ライン割当装置１００の構成の一例を示す図である。
【図３】メモリ４０のフェイルデータの一例を示す図である。
【図４】予備ライン割当装置１００における処理の一例を説明する図である。
【図５】予備ライン割当装置１００の他の構成例を示す図である。
【図６】図５に示した予備ライン割当装置１００の処理の一例を説明する図である。
【図７】図１から図６において説明した予備ライン割当装置１００の動作の一例を示すフローチャートである。
【図８】図７において説明した予備ラインの割当処理Ｓ４０４の、処理の一例を示すフローチャートである。
【図９】メモリ４０における他のフェイルデータの例を示す図である。
【図１０】予備ライン割当装置１００の他の構成例を示す図である。
【図１１】孤立フェイル検出部１５０に与えられるフェイルデータのビットマップの一例を示す図である。
【図１２】救済可否判定部１４０の一部の構成例を示す図である。
【図１３】フェイルビットのビットマップの一例を示す図である。
【図１４】本発明の一つの実施形態に係るメモリ製造方法の一例を示すフローチャートである。
【図１５】本発明の一つの実施形態に係るコンピュータ１９００のハードウェア構成の一例を示す。
【符号の説明】
【００１３】
１０・・・メモリ試験装置、２０・・・メモリ救済装置、３０・・・設定部、４０・・・メモリ、１００・・・ライン割当装置、１１０・・・ビット計数部、１２０・・・重み算出部、１３０・・・割当部、１４０・・・救済可否判定部、１４２・・・第１の乗算部、１４４・・・第２の乗算部、１４６・・・比較部、１５０・・・孤立フェイル検出部、１９００・・・コンピュータ、２０００・・・ＣＰＵ、２０１０・・・ＲＯＭ、２０２０・・・ＲＡＭ、２０３０・・・通信インターフェース、２０４０・・・ハードディスクドライブ、２０５０・・・フレキシブルディスク・ドライブ、２０６０・・・ＣＤ−ＲＯＭドライブ、２０７０・・・入出力チップ、２０８０・・・表示装置、２０８２・・・ホスト・コントローラ、２０８４・・・入出力コントローラ、２０９０・・・フレキシブルディスク、２０９５・・・ＣＤ−ＲＯＭ
【発明を実施するための最良の形態】
【００１４】
以下、発明の実施形態を通じて本発明を説明するが、以下の実施形態は請求の範囲に係る発明を限定するものではなく、また実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。【００１５】
図１は、半導体メモリ等のメモリ４０を試験するメモリ試験装置１０、およびメモリ４０のフェイルビットを救済するメモリ救済装置２０の一例を示す図である。メモリ試験装置１０は、試験対象のメモリ４０の各記憶セルが、正常に動作するか否かを試験する。メモリ試験装置１０は、メモリ４０の各記憶セルがフェイルビットであるか否かを示すフェイルデータを、ライン救済装置２０に入力してよい。メモリ４０は、例えば２次元のマトリクス状に記憶セルが配置された半導体メモリであってよい。また、メモリ４０には、記憶セルのマトリクスにおける行方向または列方向のアドレスラインに対して、それぞれ所定の数の予備ラインが予め設けられる。【００１６】
メモリ救済装置２０は、予備ライン割当装置１００および設定部３０を備える。予備ライン割当装置１００は、メモリ試験装置１０からメモリ４０のフェイルデータを受け取る。また、予備ライン割当装置１００は、当該フェイルデータに基づいて、メモリ４０においてフェイルビットを有する行方向のアドレスライン（行方向のフェイルライン）及び列方向のアドレスライン（列方向のフェイルライン）のうち、いずれのフェイルラインに予備ラインを割り当てるかを決定する。ここで、フェイルラインとは、行方向および列方向のアドレスラインのうち、フェイルビットを有するアドレスラインを指してよい。設定部３０は、予備ライン割当装置１００が決定した予備ラインの割当てを、メモリ４０に設定する。例えば設定部３０は、当該予備ラインの割当てに応じて、メモリ４０内の配線をレーザ等により溶断することで、当該割当てをメモリ４０に設定してよい。このような処理により、フェイルビットを救済したメモリ４０を製造することができる。【００１７】
図２は、予備ライン割当装置１００の構成の一例を示す図である。予備ライン割当装置１００は、ビット計数部１１０、重み算出部１２０、および割当部１３０を有する。ビット計数部１１０は、メモリ試験装置１０からメモリ４０のフェイルデータを受け取る。【００１８】
図３は、メモリ４０のフェイルデータの一例を示す図である。ビット計数部１１０は、図３に示すような、フェイルデータのビットマップを受け取ってよい。ビット計数部１１０は、当該ビットマップを格納するビットマップメモリを有してよい。なお図３においては、行方向および列方向に、１０ラインずつのアドレスラインを有するメモリ４０を一例として説明する。また図３において、行方向および列方向のアドレスラインが交差する点が、それぞれ１ビットの記憶セルに対応する。また、本例のメモリ４０におけるフェイルビットをＸ印で示す。本例では、（行アドレス、列アドレス）＝（１、１）、（１、３）、（１、５）、（１、９）、（２、１）、（３、２）、（３、４）、（３、７）、（５、３）、（６、４）、（８、４）の各ビットが、フェイルビットである。【００１９】
ビット計数部１１０は、それぞれのフェイルライン（行方向のアドレスライン１、２、３、５、６、８、および列方向のアドレスライン１、２、３、４、５、７、９）に含まれるそれぞれのフェイルビットについて、当該フェイルビットを含み、且つ当該フェイルラインとは異なる方向のフェイルラインが有するフェイルビットの個数を、直交フェイルビット数として計数する。例えば、フェイルビット（ｎ，ｍ）の行アドレスラインｎにおける直交フェイルビット数は、フェイルビット（ｎ，ｍ）を含み、且つ行アドレスラインｎと直交する列アドレスラインｍが有するフェイルビット数である（ただし、ｎ，ｍは整数）。また、フェイルビット（ｎ，ｍ）の列アドレスラインｍにおける直交フェイルビット数は、フェイルビット（ｎ，ｍ）を含み、且つ列アドレスラインｍと直交する行アドレスラインｎが有するフェイルビット数である。【００２０】
より具体的には、例えばフェイルビット（１，１）の行アドレスライン１における直交フェイルビット数は、列アドレスライン１が有するフェイルビット数であるので、本例では"２"となる。また、フェイルビット（１，１）の列アドレスライン１における直交フェイルビット数は、行アドレスライン１が有するフェイルビット数であるので、本例では"４"となる。【００２１】
ビット計数部１１０は、それぞれのフェイルビット（ｎ，ｍ）について、行アドレスラインｎにおける直交フェイルビット数と、列アドレスラインｍにおける直交フェイルビット数とを計数して、それぞれのフェイルビットごとに格納する。ビット計数部１１０は、メモリ４０の各ビットに対して、行アドレスラインにおける直交フェイルビット数を格納する行ビット数レジスタと、列アドレスラインにおける直交フェイルビット数を格納する列ビット数レジスタとを、それぞれ有してよい。【００２２】
重み算出部１２０は、それぞれのフェイルラインに含まれるフェイルビットの、当該フェイルラインにおける直交フェイルビット数に基づいて、それぞれのフェイルラインの重み係数を算出する。例えば重み算出部１２０は、当該フェイルラインにおける直交フェイルビット数がより大きいフェイルビットに対して、より小さい係数を算出してよい。そして、それぞれのフェイルラインが有するフェイルビットの係数の総和を、当該フェイルラインの重み係数として算出してよい。【００２３】
基本的には、含まれるフェイルビット数がより多いフェイルラインに対して、順次予備ラインを割り当てることにより、より多くのフェイルビットを救済することができる。しかし、メモリ４０の各記憶セルは、メモリ４０の所定の面内に形成されるので、行アドレスラインおよび列アドレスラインの双方に属するように、２次元マトリクス状に形成することが好ましい。このため、各フェイルビットは、行アドレスラインおよび列アドレスラインの双方で救済することができる。このとき、一つのフェイルビットが、行アドレスラインの予備ライン、および列アドレスラインの予備ラインの双方で救済されるように予備ラインを割り当てた場合、救済できるフェイルビットの総数が減少してしまう。【００２４】
これに対し、予備ライン割当装置１００は、各フェイルビットについて、行アドレスラインおよび列アドレスラインにおける直交フェイルビット数を求めることにより、それぞれのフェイルビットを行アドレスラインまたは列アドレスラインのいずれで救済すべきかを示す係数を取得することができる。そして、各フェイルラインが有するフェイルビットの係数の総和を求めることにより、予備ラインを割り当てるべきかを示す重み係数を、各フェイルラインについて取得することができる。【００２５】
より具体的には、重み算出部１２０は、それぞれのフェイルラインが有するフェイルビットの、当該フェイルラインにおける直交フェイルビット数の逆数の総和に基づいて、当該フェイルラインの重み係数を算出してよい。例えば、行アドレスライン１が有するフェイルビット（１，１）、（１，３）、（１，５）、（１，９）の、行アドレスライン１における直交フェイルビット数は、２、２、１、１となる。重み算出部１２０は、行アドレスライン１の重み係数として、これらの直交フェイルビット数の逆数の総和、すなわち１／２＋１／２＋１／１＋１／１＝３を算出してよい。重み係数算出部１２０は、フェイルラインごとに重み係数を算出して格納してよい。重み係数算出部１２０は、アドレスラインごとに設けられ、対応するアドレスラインの重み係数を格納する重みレジスタを有してよい。【００２６】
割当部１３０は、重み算出部１２０が算出した重み係数の大小関係に基づいて、いずれのフェイルラインに予備ラインを割り当てるかを決定する。例えば割当部１３０は、重み係数がより大きいフェイルラインに予備ラインを割り当ててよい。例えば図３に示した例では、行アドレスライン１の重み係数が最も大きいので、割当部１３０は、行アドレスライン１に、行方向の予備ラインを割り当ててよい。【００２７】
また、割当部１３０には、メモリ４０に設けられた行方向および列方向の予備ラインのそれぞれの本数が予め通知されてよい。例えば割当部１３０には、使用者等により、予備ラインの本数が予め通知される。割当部１３０は、通知された行方向および列方向の予備ラインの本数をそれぞれ格納する初期予備ライン数レジスタを有してよい。また、割当部１３０は、いずれかのフェイルラインに予備ラインを割り当てた場合に、該当する方向の予備ラインの本数を減じることにより算出した、各方向の残存予備ライン数を格納する残存予備ライン数レジスタを更に有してよい。割当部１３０は、残存予備ライン数がゼロでないことを条件として、当該方向の予備ラインを、フェイルラインに割り当ててよい。【００２８】
図４は、予備ライン割当装置１００における処理の一例を説明する図である。図３において説明したように、割当部１３０は、重み係数が最も大きいフェイルライン（図３では、行アドレスライン１）に、対応する方向の予備ラインを割り当てる。このとき、割当部１３０は、当該フェイルラインに予備ラインを割り当てた旨を、ビット計数部１１０に通知してよい。【００２９】
ビット計数部１１０は、予備ラインが割り当てられたフェイルラインに含まれるフェイルビットを除外した場合の、それぞれのフェイルビットの行方向および列方向における直交フェイルビット数を算出する。ビット計数部１１０は、予備ラインが割り当てられたフェイルラインに含まれるフェイルビットを除外した場合のフェイルデータのビットマップを格納する更新ビットマップメモリを更に有してよい。【００３０】
本例のビット計数部１１０は、図４に示すように、行アドレスライン１が有するフェイルビットが救済されたものとして、それぞれのフェイルビットの直交フェイルビット数を再計算する。ビット計数部１１０は、再計算した行方向および列方向の直交フェイルビット数をそれぞれのフェイルビットについて新たに格納する、行方向および列方向の再計算ビット数レジスタを更に有してよい。【００３１】
重み算出部１２０は、ビット計数部１１０が再計算して新たに格納した直交フェイルビット数に基づいて、予備ラインが割り当てられたフェイルラインに含まれるフェイルビットを除外した場合の、それぞれのフェイルラインの重み係数を算出する。例えば、本例の行アドレスライン２の重み係数は、行アドレスライン１のフェイルビットが救済されたことにより、１／２から１に再計算される。重み算出部１２０は、フェイルラインごとに重み係数を再計算して格納する。重み算出部１２０は、アドレスラインごとに設けられ、対応するアドレスラインに対して再計算された重み係数を格納する、更新重みレジスタを更に有してよい。【００３２】
割当部１３０は、重み算出部１２０が新たに格納した重み係数に基づいて、次に予備ラインを割り当てるべきフェイルラインを選択する。例えば割当部１３０は、更新された重み係数が最も大きいフェイルラインに、次の予備ラインを割り当ててよい。また、例えば図４の行アドレスライン３と列アドレスライン４のように、重み係数が同一の値となる場合も考えられる。この場合、割当部１３０は、使用者等により予め指定される方向のフェイルラインを優先して、予備ラインを割り当ててよい。また、割当部１３０は、残存予備ライン数がより大きい方向のフェイルラインを優先して、予備ラインを割り当ててもよい。また、割当部１３０は、重み係数が同一である複数のフェイルラインに対して、同時に予備ラインを割り当ててもよい。【００３３】
このような処理を繰り返すことにより、救済できるフェイルビット数が最大化されるように、予備ラインを割り当てることができる。このため、全てのフェイルビットが救済されるような予備ラインの割り当ての解を、効率よく検出することができる。【００３４】
図５は、予備ライン割当装置１００の他の構成例を示す図である。本例における予備ライン割当装置１００は、図１から図４に関連して説明した予備ライン割当装置１００の構成に対して、救済可否判定部１４０を更に備える。本例の予備ライン割当装置１００における他の構成要素は、図１から図４に関連して説明した予備ライン割当装置１００と同一であってよい。【００３５】
救済可否判定部１４０は、図１から図４において説明したように予備ラインを順次割り当てた場合に、全てのフェイルビットを救済できるか否かを判定する。例えば救済可否判定部１４０は、割当部１３０が、いずれかのフェイルラインに予備ラインを割り当てる毎に、全てのフェイルビットを救済できる可能性が残っているか否かを判定してよい。【００３６】
一例として、救済可否判定部１４０は、残存予備ライン数がゼロとなった場合に、救済されていないフェイルビットが残っている場合に、全てのフェイルビットを救済できる可能性が無くなったと判定してよい。また、残存予備ライン数がゼロでない場合においても、救済可否判定部１４０は、例えば図１０から図１２において後述するような方法で、全てのフェイルビットを救済できる可能性が残っているか否かを判定してよい。【００３７】
割当部１３０は、いずれのフェイルラインに予備ラインを割り当てたかを、救済可否判定部１４０に通知してよい。救済可否判定部１４０は、当該通知の内容と、ビット計数部１１０、重み算出部１２０、および割当部１３０における各レジスタ、各メモリの情報とに基づいて、全てのフェイルビットを救済できる可能性が残っているか否かを判定してよい。【００３８】
例えば救済可否判定部１４０は、当該フェイルラインに予備ラインを割り当てた結果、割当部１３０の残存予備ライン数レジスタが格納したライン数がゼロとなり、且つビット計数部１１０の更新ビットマップメモリが格納したビットマップにフェイルデータが残存する場合に、全てのフェイルビットを救済できる可能性が無いと判定してよい。また、救済可否判定部１４０は、当該フェイルラインに予備ラインを割り当てた結果、一の方向の残存予備ライン数がゼロとなり、且つ他の方向の残存予備ライン数が当該他の方向のフェイルライン数より少なくなった場合に、全てのフェイルビットを救済できる可能性が無いと判定してもよい。【００３９】
図６は、図５に示した予備ライン割当装置１００の処理の一例を説明する図である。本例では、残存するフェイルビットが（行アドレス、列アドレス）＝（１、１）、（１、２）、（２、３）、（２、４）、（２、５）、（２、６）、（３、４）、（３、５）、（３、６）の各ビットであり、行方向の残存予備ライン数が１であり、列方向の残存予備ライン数が４である第１の状態の場合を説明する。図６に示す第１の状態は、メモリ４０の初期状態であってよく、また図１から図５において説明した処理において、いくつかの予備ラインが割り当てられた後の状態であってもよい。【００４０】
図１から図４において説明したように、重み算出部１２０は、それぞれのアドレスラインに対して重み係数を算出する。そして、割当部１３０は、重み係数が最も大きいフェイルラインに、予備ラインを割り当てる。本例では、行アドレスライン２の重み係数が最も大きいので、行アドレスライン２に、行方向の予備ラインを割り当てる。この結果、行方向の残存予備ライン数はゼロとなる。また、列方向のフェイルライン数は"５"となり、列方向の残存予備ライン数"４"より大きい。このような場合、救済可否判定部１４０は、いずれかのフェイルビットを救済できないと判定して、その旨を割当部１３０に通知する。【００４１】
割当部１３０は、当該通知を受けた場合に、予備ラインが既に割り当てられているフェイルラインのいずれかを第１のフェイルラインとして、第１のフェイルラインに対する予備ラインの割り当てを解除する。本例の割当部１３０は、直前に予備ラインを割り当てた行アドレスライン２を第１のフェイルラインとして、予備ラインの割り当てを解除する。このとき、ビット計数部１１０、重み算出部１２０、および割当部１３０における各レジスタおよび各メモリの内容は、第１のフェイルラインに予備ラインを割り当てる前の状態に戻される。【００４２】
例えば重み算出部１２０は、救済可否判定部１４０が、いずれかのフェイルビットを救済できないと判定した場合に、第１のフェイルラインに予備ラインを割当てる前の重み係数を再計算してよい。また、ビット計数部１１０、重み算出部１２０、および割当部１３０は、各レジスタおよび各メモリについて、フェイルラインに予備ラインを割り当てる毎のそれぞれの状態を格納するキャッシュメモリを有してよい。【００４３】
また、割当部１３０は、救済可否判定部１４０から、いずれかのフェイルビットを救済できない旨の通知を受けた場合に、第１のフェイルラインが有するフェイルビットを含み、且つ第１のフェイルラインとは異なる方向の、それぞれの第２のフェイルラインを選択して、予備ラインを割り当てる。本例の割当部１３０は、行アドレスライン２が有するフェイルビット（２，３）、（２，４）、（２，５）、（２，６）を含み、且つ行アドレスライン２と直交する４本の列アドレスライン３、４、５、６に、列方向の予備ラインを割り当てる。【００４４】
本例では、第２フェイルラインとして選択されたアドレスラインの本数が、当該方向に残存する予備ライン数以下であるので、救済可否判定部１４０は、全てのフェイルビットを救済できる可能性がある旨を、割当部１３０に通知する。ビット計数部１１０および重み算出部１２０は、それぞれの第２フェイルラインに予備ラインを割り当てた状態の、フェイルデータのビットマップ、直交フェイルビット数、重み係数等を再計算する。【００４５】
そして、割当部１３０は、再計算された重み係数に基づいて、次に予備ラインを割り当てるべきフェイルラインを選択する。本例の割当部１３０は、行アドレスライン１の重み係数が最も大きいので、行アドレスライン１に、行方向の予備ラインを割り当てる。このとき、救済可否判定部１４０は、行方向の残存予備ライン数がゼロでなく、且つ当該予備ラインを割り当てた場合に残存するフェイルビットがゼロとなるので、当該割当により、全てのフェイルビットが救済できた旨を割当部１３０に通知してよい。割当部１３０は、当該通知を受けた場合に、予備ラインの割当の態様を確定して、設定部３０に通知してよい。【００４６】
以上のように、第１のフェイルラインに予備ラインを設定すると全てのフェイルビットを救済できる可能性が無いと判定された場合、予備ライン割当装置１００は、第１のフェイルラインに対する割り当てを解除することにより、第１のフェイルラインを割り当てた状態での予備ラインの割り当て解を探索するそれ以降の処理を省略することができる。このため、処理時間を短縮することができる。また、第１のフェイルラインに予備ラインを設定しない場合、第１のフェイルラインに含まれるフェイルビットは、直交する第２のフェイルラインに予備ラインを割り当てなければ救済できない。本例のように、第１のフェイルラインに対する割り当てを解除した場合に、直交する第２のフェイルラインに強制的に予備ラインを割り当てることにより、予備ラインの割り当て解を探索する処理の効率を向上させることができる。【００４７】
また、第２フェイルラインとして選択されたアドレスラインの本数が、当該方向に残存する予備ライン数より多い場合、救済可否判定部１４０は、全てのフェイルビットを救済できる可能性が無い旨を、割当部１３０に通知する。この場合、第１の状態における残存フェイルビットと、残存予備ラインとの組み合わせでは、全てのフェイルビットを救済できる予備ラインの割り当て解が存在しない。【００４８】
このため割当部１３０は、第１の状態となる直前に、フェイルラインに割り当てた予備ラインを更に解除する。つまり割当部１３０は、当該フェイルラインに予備ラインを割り当てた結果、残存フェイルビットおよび残存予備ラインが第１の状態となった、フェイルラインに対する予備ラインの割り当てを更に解除する。そして割当部１３０は、予備ラインの割り当てを解除したフェイルラインのフェイルビットを含み、且つ当該フェイルラインに直交するフェイルラインに予備ラインを強制的に割り当てる。【００４９】
このように、予備ライン割当装置１００は、全てのフェイルビットを救済できる可能性が無い場合に、予備ラインの割り当てを順に解除して、直交するフェイルラインに予備ラインを強制的に割り当てる。そして、予備ラインの割り当て解を探索することにより、効率よく割り当て解を検出することができる。【００５０】
図７は、図１から図６において説明した予備ライン割当装置１００の動作の一例を示すフローチャートである。上述したように、まずビット計数部１１０は、各フェイルビットについて、行方向および列方向の直交フェイルビット数を計数する（Ｓ４００）。【００５１】
次に、重み算出部１２０は、各フェイルラインに含まれるフェイルビットの直交フェイルビット数に基づいて、それぞれのフェイルラインの重み係数を算出する（Ｓ４０２）。そして、予備ライン割当装置１００は、図１から図６において説明したように、フェイルラインの重み係数に基づいて、予備ラインの割当処理を行う（Ｓ４０４）。【００５２】
そして予備ライン割当装置１００は、Ｓ４０４の処理により全てのフェイルビットが救済できるか否かを判定する（Ｓ４０６）。全てのフェイルビットが救済できる場合、設定部３０はメモリ４０に対して救済処理を行う（Ｓ４０８）。また、いずれかのフェイルビットが救済できない場合、予備ライン割当装置１００は、例えばその旨を使用者等に通知することにより、救済不可の処理を行う（Ｓ４１０）。【００５３】
図８は、図７において説明した予備ラインの割当処理Ｓ４０４の、処理の一例を示すフローチャートである。上述したように、割当部１３０は、重み係数が最大のフェイルラインに予備ラインを割り当てる（Ｓ５００）。次に、救済可否判定部１４０は、割当部１３０が一つの予備ラインをフェイルラインに割り当てた場合に、予め定められた判定基準に基づいて、全てのフェイルビットを救済できる可能性が残っているか否かを判定する（Ｓ５０２）。例えば救済可否判定部１４０は、上述したように、残存フェイルビットと、残存予備ライン数とに基づいて、全てのフェイルビットを救済できるか否かを判定してよい。【００５４】
Ｓ５０２において全てのフェイルビットを救済できる可能性が残っていると判定された場合、ビット計数部１１０および重み算出部１２０の各レジスタおよび各メモリのデータを更新する。例えば重み算出部１２０は、重み係数を更新する（Ｓ５０４）。また、救済可否判定部１４０は、救済されていないフェイルビットが存在するか否かを判定する（Ｓ５０６）。Ｓ５０６において、救済されていないフェイルビットが存在すると判定された場合、Ｓ５００からの処理を繰り返して、予備ラインを順次割り当てる。また、Ｓ５０６において、救済されていないフェイルビットが存在しないと判定された場合、予備ラインの当該割り当ての態様で、全てのフェイルビットが救済可能であると判定する（Ｓ５０８）。この場合、図７において説明したように設定部３０により、救済処理Ｓ５０８を行う。【００５５】
また、Ｓ５０２において、全てのフェイルビットを救済できる可能性が無いと判定された場合、割当部１３０は、直前に設定した予備ラインの割り当てを解除する（Ｓ５１０）。そして、ビット計数部１１０および重み算出部１２０の各レジスタおよび各メモリのデータを、当該予備ラインを割り当てる前の状態に戻す。例えば重み算出部１２０は、当該予備ラインを割り当てる前の状態の重み係数を再計算してよい（Ｓ５１２）。【００５６】
次に、割当部１３０は、予備ラインの割り当てを解除した第１のフェイルラインのフェイルビットを含み、第１のフェイルラインと直交する第２のフェイルラインを選択して、予備ラインを割り当てる（Ｓ５１４）。次に、救済可否判定部１４０は、全てのフェイルビットを救済できる可能性があるか否かを判定する（Ｓ５１６）。【００５７】
Ｓ５１６において、全てのフェイルビットを救済できる可能性があると判定された場合、当該予備ラインの割り当てに基づいて、Ｓ５０４以降の処理を行う。また、Ｓ５１６においていずれかのフェイルビットを救済できないと判定された場合、割当部１３０は、更に予備ラインの割り当てを解除できるか否かを判定してよい（Ｓ５１８）。例えば、既にメモリ４０の初期状態にまで遡って予備ラインの割り当てを解除している場合、これ以上の予備ラインの割り当てを解除できないと判定してよい。【００５８】
Ｓ５１８において、更に予備ラインの割り当てを解除できると判定した場合、割当部１３０は、Ｓ５１０の処理に戻り、直前に割り当てた予備ラインを解除する。また、Ｓ５１８において、更に予備ラインの割り当てを解除できないと判定した場合、メモリ４０に対しての全てのフェイルビットを救済できる予備ラインの割り当て解は存在しないとして、処理を終了する。この場合、図７において説明した救済不可処理Ｓ４１０を実行する。以上のような処理により、予備ラインの割り当て解を効率よく検出することができる。【００５９】
また、以上の例においては、予備ラインを割り当てる毎に、各フェイルラインの重み係数を更新する例を説明した。他の例では、予備ライン割当装置１００は、各フェイルラインの重み係数を更新せずともよい。この場合、予備ライン割当装置１００は、図８において説明した、重み係数更新処理Ｓ５０４および重み係数再計算処理Ｓ５１２を省略してよい。このような処理によっても、予備ラインの割り当て解を効率よく検出することができる。【００６０】
また、図８の処理例では、Ｓ５０２において、全てのフェイルビットを救済できないと判定された場合に、直前に割り当てた予備ラインを解除する（Ｓ５１２）。他の例におけるＳ５１２の処理では、Ｓ５００において最初に割り当てた予備ラインを解除してもよい。この場合、Ｓ５１２の処理では、ビット計数部１１０および重み算出部１２０の各レジスタおよび各メモリは、初期状態に戻される。また、Ｓ５００の処理の前に、割当部１３０は、予め定められた数のフェイルビットがあるフェイルラインに、予備ラインを予め割り当ててよい。【００６１】
図９は、メモリ４０における他のフェイルデータの例を示す図である。また、本例のメモリ４０の記憶領域は、列方向および行方向の少なくとも一方において、複数の記憶ブロックに分割される。図９の例では、メモリ４０の記憶領域は、行方向に３つのブロックに分割され、列方向に２つのブロックに分割される。メモリ４０は、それぞれの記憶ブロックごとに、行方向および列方向の予備ラインを有してよい。【００６２】
係るメモリ４０に対して、図８において説明したＳ５０２の処理において、救済可否判定部１４０がいずれかのフェイルビットを救済できないと判定した場合、直前の第１のフェイルライン割り当てた予備ラインを解除する（Ｓ５１０）。そして、Ｓ５１４の処理において割当部１３０は、第１のフェイルラインと同一の方向のフェイルであり、且つ記憶ブロック毎のフェイルビット数が、第１のフェイルラインと同一となる第３のフェイルラインを選択して、予備ラインを強制的に割り当ててよい。このとき、割当部１３０は、前述した第２のフェイルライン、および第３のフェイルラインの双方に対して、予備ラインを割り当ててよい。【００６３】
例えば、図８において説明したＳ５００の処理において、図９に示した行アドレスライン１に予備ラインを割り当てた場合を説明する。この場合において、いずれかのフェイルビットを救済できないと判定された場合（Ｓ５０２）、Ｓ５１４の処理においては、まず第２のフェイルラインとして、列アドレスライン１、２、７、８、９が選択される。更に、行アドレスライン２が有するフェイルビットの記憶ブロック毎の個数は、行アドレスライン１が有するフェイルビットの記憶ブロック毎の個数と同一となるので、割当部１３０は、行アドレスライン２のフェイルビットを含み、且つ行アドレスライン２と直交する列アドレスライン２、３、６、７、９を第３のフェイルラインとして選択する。【００６４】
そして割当部１３０は、選択した第２のフェイルラインおよび第３のフェイルラインに、強制的に予備ラインを割り当てる（Ｓ５１４）。このように、記憶ブロック毎に予備ラインが設けられている場合において、あるフェイルラインに予備ラインを割り当てると全てのフェイルビットを救済できない場合、当該フェイルラインに対して、記憶ブロック毎のフェイルビット数が同一であるフェイルラインも、予備ラインを割り当てた場合には全てのフェイルビットを救済できない可能性が高い。係るフェイルラインについても、直交する第３のフェイルラインに強制的に予備ラインを割り当てることにより、予備ラインの割り当て解を更に効率よく探索することができる。【００６５】
図１０は、予備ライン割当装置１００の他の構成例を示す図である。本例の予備ライン割当装置１００は、図５に関連して説明した予備ライン割当装置１００の構成に加え、孤立フェイル検出部１５０を更に備える。他の構成要素は、図５に関連して説明した予備ライン割当装置１００と同一であってよい。【００６６】
孤立フェイル検出部１５０は、当該フェイルビットを含む列方向および行方向のフェイルラインに、他のフェイルビットが無い場合に、当該フェイルビットを孤立フェイルビットとして検出する。つまり、孤立フェイル検出部１５０は、列方向のあるフェイルラインに含まれるフェイルビットが一つだけであり、且つ当該フェイルビットを含み当該フェイルラインと直交する行方向のフェイルラインに、他のフェイルビットが含まれない場合に、当該フェイルビットを孤立フェイルビットとして検出する。孤立フェイル検出部１５０は、ビット計数部１１０が順次更新して格納しているフェイルデータのビットマップに基づいて、それぞれの状態における孤立フェイルビットを順次検出してよい。【００６７】
図１１は、孤立フェイル検出部１５０に与えられるフェイルデータのビットマップの一例を示す図である。上述したように、孤立フェイル検出部１５０は、当該ビットマップに基づいて、孤立フェイルビットを検出してよい。本例では、孤立フェイル検出部１５０は、フェイルビット（１，１）、（２，２）、（３，３）、（４，４）、（５，５）の５つのフェイルビットを、孤立フェイルビットとして検出する。【００６８】
また、救済可否判定部１４０は、図８に示したＳ５０２およびＳ５１６の処理において、孤立フェイルビット数および残存予備ライン数に基づいて、全てのフェイルビットを救済できる可能性が残っているか否かを判定してよい。例えば救済可否判定部１４０は、行方向および列方向の残存予備ライン数の和が、孤立フェイル数より少ない場合に、全てのフェイルビットを救済できる可能性が無いと判定してよい。【００６９】
また、割当部１３０は、図８において説明したＳ５００の処理において、孤立フェイル数および残存予備ライン数に基づいて、強制的に予備ラインを割り当てるべきフェイルラインを選択してよい。例えば割当部１３０は、孤立フェイルビット数から、列方向の残存予備ラインの本数を減じた減算結果に応じた本数の行方向の予備ラインを、孤立フェイルビットを含む任意の行方向のフェイルラインに割り当ててよい。【００７０】
例えば、孤立フェイルビット数が"５"であり、列方向の残存予備ラインの本数が"２"である場合、割当部１３０は、３本の行方向の予備ラインを、孤立フェイルビットを含むいずれか３本の行方向のフェイルラインに割り当てる。同様に、孤立フェイルビット数が"５"であり、行方向の残存予備ラインの本数が"４"である場合、割当部１３０は、１本の列方向の予備ラインを、孤立フェイルビットを含むいずれか１本の列方向のフェイルラインに割り当てる。【００７１】
各方向の予備ラインで救済できる孤立フェイルビット数の最大値は、当該方向の残存予備ライン数となる。このため、行方向または列方向の少なくともいずれかの残存予備ライン数ａが孤立フェイルビット数ｂより少ない場合、他の方向の予備ラインでは、少なくともｂ−ａ個の孤立フェイルビット数を救済しなければならない。【００７２】
このため、上述したように、孤立フェイル数および残存予備ライン数に基づいて、強制的に予備ラインを割り当てることにより、更に効率よく予備ラインの割り当て解を探索することができる。また、孤立フェイル検出部１５０は、重み係数に基づいて割当部１３０が予備ラインをフェイルラインに割当てる毎に、当該フェイルラインに含まれるフェイルビットを除外した状態における、孤立フェイルビットを検出してよい。孤立フェイル検出部１５０は、各状態における孤立フェイルビット数を格納するレジスタを有してよい。【００７３】
また、まだ予備ラインが割り当てられておらず、未救済のフェイルビットの全てが孤立フェイルビットとなった場合であって、孤立フェイルビット数が残存予備ライン数より少ない場合、救済可能であることが確定する。この場合、割当部１３０は、残存している全てのフェイルラインに予備ラインを割り当てて、割当処理を終了してよい。例えば割当部１３０は、使用者等により予め指定された方向の予備ラインを優先して、残存しているフェイルラインに割り当ててよい。【００７４】
また、図１０および図１１に関連して説明した、孤立フェイルビットに係る処理は、図９に関連して説明した記憶ブロック毎に行ってよい。例えば、救済可否判定部１４０は、いずれかの記憶ブロックにおいて、行方向および列方向の残存予備ライン数の和が、孤立フェイル数より少ない場合に、全てのフェイルビットを救済できる可能性が無いと判定してよい。【００７５】
図１２は、救済可否判定部１４０の一部の構成例を示す図である。本例の救済可否判定部１４０は、図１から図１１に関連して説明した機能を実行する構成に加え、第１の乗算部１４２、第２の乗算部１４４、および比較部１４６を有する。【００７６】
第１の乗算部１４２は、列方向のフェイルラインに含まれるフェイルビットの個数の最大値と、列方向の残存予備ラインの本数とを乗算した第１の乗算値を算出する。つまり、第１の乗算値は、列方向の残存予備ラインにより救済可能なフェイルビットの最大値を示す。また、第２の乗算部１４４は行方向のフェイルラインに含まれるフェイルビットの個数の最大値と、行方向の残存予備ラインの本数とを乗算した第２の乗算値を算出する。つまり、第２の乗算値は、行方向の残存予備ラインにより救済可能なフェイルビットの最大値を示す。【００７７】
比較部１４６は、第１の乗算値および第２の乗算値の和が、残存フェイルビットの総数より小さいか否かを判定する。第１の乗算値および第２の乗算値の和が、残存フェイルビットの総数より小さい場合、残存予備ラインでは全てのフェイルビットを救済できない。この場合、比較部１４６は、その旨を割当部１３０に通知する。【００７８】
図１３は、フェイルビットのビットマップの一例を示す図である。本例のフェイルビットの総数は１３であり、行方向および列方向の残存予備ラインの本数はそれぞれ"３"である。【００７９】
第１の乗算部１４２は、行方向のフェイルラインに含まれるフェイルビットの個数の最大値を検出する。図１３に示すように、本例における当該最大値は"２"である。第１の乗算部１４２は、残存予備ラインの本数"３"と、最大値"２"とを乗算して、第１の乗算値"６"を算出する。【００８０】
同様に、第２の乗算部１４４は、列方向のフェイルラインに含まれるフェイルビットの個数の最大値を検出する。図１３に示すように、本例における当該最大値は"２"である。第２の乗算部１４４は、残存予備ラインの本数"３"と、最大値"２"とを乗算して、第２の乗算値"６"を算出する。【００８１】
本例では、第１の乗算値および第２の乗算値の和"１２"が、残存フェイルビット数"１３"より小さい。このため比較部１４６は、全てのフェイルビットを救済できない旨を、割当部１３０に通知する。このような処理により、全てのフェイルビットを救済できる可能性が無くなったことを、より早期に検出することができるので、予備ラインの割り当て解を効率よく探索することができる。【００８２】
また、救済可否判定部１４０は、図１２および図１３に関連して説明した第１の乗算値および第２の乗算値を用いた処理を、図９に関連して説明した記憶ブロック毎に行ってよい。例えば、救済可否判定部１４０は、いずれかの記憶ブロックにおける、第１の乗算値および第２の乗算値の和が、残存フェイルビット数より小さい場合に、全てのフェイルビットを救済できる可能性が無いと判定してよい。【００８３】
図１４は、本発明の一つの実施形態に係るメモリ製造方法の一例を示すフローチャートである。当該メモリ製造方法は、図１から図１３において説明した予備ライン割当方法およびメモリ救済方法を用いて、半導体メモリ等のメモリ４０を製造する。【００８４】
まず、メモリ形成段階において、複数の予備ラインが設けられたメモリ４０を形成する（Ｓ６００）。次に、メモリ４０を試験して、メモリ４０のフェイルデータを生成する（Ｓ６０２）。【００８５】
次に、予備ライン割当段階において、メモリ４０においてフェイルビットを有する行方向のフェイルライン及び列方向のフェイルラインのうち、いずれのフェイルラインに予備ラインを割り当てるかを決定する（Ｓ６０４）。Ｓ６０４は、図１から図１３において説明した予備ライン割当装置１００を用いて行ってよい。【００８６】
そして、決定した予備ラインの割り当てを、メモリ４０に設定してメモリ４０を救済することにより、良品のメモリ４０を製造する（Ｓ６０６）。Ｓ６０６は、図１から図１３において説明した設定部３０を用いて行ってよい。このような処理により、良品のメモリ４０を効率よく製造することができる。【００８７】
図１５は、本発明の一つの実施形態に係るコンピュータ１９００のハードウェア構成の一例を示す。コンピュータ１９００は、与えられるプログラムに基づいて、図１から図１４において説明した予備ライン割当装置１００として機能してよい。【００８８】
コンピュータ１９００が予備ライン割当装置１００として機能する場合、プログラムは、コンピュータ１９００を、図１から図１４において説明したビット計数部１１０、重み算出部１２０、割当部１３０、救済可否判定部１４０、および孤立フェイル検出部１５０のすくなくともいずれかとして機能させてよい。例えばプログラムは、ＣＰＵ２０００を、ビット計数部１１０、重み算出部１２０、割当部１３０、救済可否判定部１４０、および孤立フェイル検出部１５０として機能させてよく、またハードディスクドライブ２０４０またはＲＡＭ２０２０を、ビット計数部１１０、重み算出部１２０、および割当部１３０に設けられる各レジスタおよび各メモリとして機能させてよい。【００８９】
コンピュータ１９００は、ＣＰＵ周辺部、入出力部、及びレガシー入出力部を備える。ＣＰＵ周辺部は、ホストコントローラ２０８２により相互に接続されるＣＰＵ２０００、ＲＡＭ２０２０、グラフィックコントローラ２０７５、及び表示装置２０８０を有する。入出力部は、入出力コントローラ２０８４によりホストコントローラ２０８２に接続される通信インターフェース２０３０、ハードディスクドライブ２０４０、及びＣＤ−ＲＯＭドライブ２０６０を有する。レガシー入出力部は、入出力コントローラ２０８４に接続されるＲＯＭ２０１０、フレキシブルディスク・ドライブ２０５０、及び入出力チップ２０７０を有する。【００９０】
ホストコントローラ２０８２は、ＲＡＭ２０２０と、高い転送レートでＲＡＭ２０２０をアクセスするＣＰＵ２０００及びグラフィックコントローラ２０７５とを接続する。ＣＰＵ２０００は、ＲＯＭ２０１０及びＲＡＭ２０２０に格納されたプログラムに基づいて動作して、各部の制御を行う。グラフィックコントローラ２０７５は、ＣＰＵ２０００等がＲＡＭ２０２０内に設けたフレーム・バッファ上に生成する画像データを取得して、表示装置２０８０上に表示させる。これに代えて、グラフィックコントローラ２０７５は、ＣＰＵ２０００等が生成する画像データを格納するフレーム・バッファを、内部に含んでもよい。【００９１】
入出力コントローラ２０８４は、ホストコントローラ２０８２と、比較的高速な入出力装置である通信インターフェース２０３０、ハードディスクドライブ２０４０、ＣＤ−ＲＯＭドライブ２０６０を接続する。通信インターフェース２０３０は、ネットワークを介して他の装置と通信する。例えば通信インターフェイス２０３０は、メモリ試験装置１０および設定部３０と通信してよい。ハードディスクドライブ２０４０は、コンピュータ１９００内のＣＰＵ２０００が使用するプログラム及びデータを格納する。ＣＤ−ＲＯＭドライブ２０６０は、ＣＤ−ＲＯＭ２０９５からプログラム又はデータを読み取り、ＲＡＭ２０２０を介してハードディスクドライブ２０４０に提供する。【００９２】
また、入出力コントローラ２０８４には、ＲＯＭ２０１０と、フレキシブルディスク・ドライブ２０５０、及び入出力チップ２０７０の比較的低速な入出力装置とが接続される。ＲＯＭ２０１０は、コンピュータ１９００が起動時に実行するブート・プログラム、コンピュータ１９００のハードウェアに依存するプログラム等を格納する。フレキシブルディスク・ドライブ２０５０は、フレキシブルディスク２０９０からプログラム又はデータを読み取り、ＲＡＭ２０２０を介してハードディスクドライブ２０４０に提供する。入出力チップ２０７０は、フレキシブルディスク・ドライブ２０５０、パラレル・ポート、シリアル・ポート、キーボード・ポート、マウス・ポート等を介して各種の入出力装置を接続する。【００９３】
ＲＡＭ２０２０を介してハードディスクドライブ２０４０に提供されるプログラムは、フレキシブルディスク２０９０、ＣＤ−ＲＯＭ２０９５、又はＩＣカード等の記録媒体に格納されて利用者によって提供される。プログラムは、記録媒体から読み出され、ＲＡＭ２０２０を介してコンピュータ１９００内のハードディスクドライブ２０４０にインストールされ、ＣＰＵ２０００において実行される。【００９４】
当該プログラムは、コンピュータ１９００にインストールされる。当該プログラムは、ＣＰＵ２０００等に働きかけて、コンピュータ１９００を、前述した予備ライン割当装置１００の各構成要素として機能させる。【００９５】
以上に示したプログラムは、外部の記録媒体に格納されてもよい。記録媒体としては、フレキシブルディスク２０９０、ＣＤ−ＲＯＭ２０９５の他に、ＤＶＤおよびＣＤ等の光学記録媒体、ＭＯ等の光磁気記録媒体、テープ媒体、ＩＣカード等の半導体メモリ等を用いることができる。また、専用通信ネットワークまたはインターネットに接続されたサーバシステムに設けたハードディスク又はＲＡＭ等の記憶装置を記録媒体として使用して、ネットワークを介してプログラムをコンピュータ１９００に提供してもよい。【００９６】
以上、実施形態を用いて本発明を説明したが、本発明の技術的範囲は上記実施形態に記載の範囲には限定されない。上記実施形態に、多様な変更又は改良を加えることができる。そのような変更又は改良を加えた形態も本発明の技術的範囲に含まれ得ることが、請求の範囲の記載から明らかである。【００９７】
以上説明したように、本例における予備ライン割当装置１００によれば、予備ラインの割り当て解を効率よく探索することができる。また、メモリ救済装置２０によれば、メモリを効率よく救済することができる。
【図１】
2009013832.tif 000003
【図２】
2009013832.tif 000004
【図３】
2009013832.tif 000005
【図４】
2009013832.tif 000006
【図５】
2009013832.tif 000007
【図６】
2009013832.tif 000008
【図７】
2009013832.tif 000009
【図８】
2009013832.tif 000010
【図９】
2009013832.tif 000011
【図１０】
2009013832.tif 000012
【図１１】
2009013832.tif 000013
【図１２】
2009013832.tif 000014
【図１３】
2009013832.tif 000015
【図１４】
2009013832.tif 000016
【図１５】
2009013832.tif 000017
【国際調査報告】
2009013832.tif 000018
2009013832.tif 000019
2009013832.tif 000020
2009013832.tif 000021