(57)【特許請求の範囲】
【請求項１】
メモリ・セル・ブロックに分割されたフラッシュＥＥＰＲＯＭアレイのクリーン・アップにあって、ブロックには有効データおよび無効データを含むセクタとしてデータが格納され、ブロック毎に消去可能であって、当該ブロック中の全ての有効データがアレイの他のブロックに書き込まれた後、当該ブロック全体が消去され、
各ブロックに対する第１の比較・重み付け動作によって、すなわち、各ブロックについて、それに含まれる無効セクタの数を全ての他のブロックに含まれる無効セクタの数と比較しその比較により得られる値に重みをつけて第１の値とする動作によって、各ブロックについて第１の値を決定し、
各ブロックに対する第２の比較・重み付け動作によって、すなわち、各ブロックについて、それの受けた消去回数と、最も多くの消去を受けたブロックの消去回数との差を求めそれにより得られる値に重みをつけて第２の値とする動作によって、各ブロックについて第２の値を決定し、
各ブロックについて第１の値および第２の値を合計してクリーン・アップすべきブロックを決定する
ことを特徴とする、クリーン・アップすべきブロックを決定する方法。
【請求項２】
請求項１記載の方法において、
前記第１の比較・重み付け動作において与えられる第１の重みと、前記第２の比較・重み付け動作において与えられる第２の重みとの選定は、既に受けた消去回数がより少ない方のブロックがクリーン・アップ対象として選択されるように、行われている
ことを特徴とする、クリーン・アップすべきブロックを決定する方法。
【請求項３】
請求項１記載の方法において、前記第１の比較・重み付け動作において与えられる第１の重みと、前記第２の比較・重み付け動作において与えられる第２の重みとの選定は、
フラッシュＥＥＰＲＯＭアレイへの書込みのための空きが必要であるときは、含まれる無効セクタの数が多い方のブロックがクリーン・アップ対象として選択されように行われ、
空きを得るためのクリーン・アップの必要性はないけれどもクリーン・アップが可能であるときは、既に受けた消去回数がより少ない方のブロックがクリーン・アップ対象として選択されるように行われる
ことを特徴とする、クリーン・アップすべきブロックを決定する方法。
【請求項４】
請求項３記載の方法において、空きを得るためのクリーン・アップの必要性はないけれどもクリーン・アップが可能であるときのクリーン・アップは、既に受けた消去回数に５００以上の差があるときに開始され、受けた消去回数がより少ない方のブロックがクリーン・アップ対象として選択されるように行われる
ことを特徴とする、クリーン・アップすべきブロックを決定する方法。
【請求項５】
請求項１記載の方法において、
フラッシュＥＥＰＲＯＭアレイへの書込みのための空きが必要であるときは、前記第１の比較・重み付け動作において第１の重み＝０．８が与えられ、前記第２の比較・重み付け動作において第２の重み＝−０．２が与えられ、
クリーン・アップの必要性はないけれどもクリーン・アップが可能であるときは、前記第１の比較・重み付け動作において第１の重み＝０．２が与えられ、前記第２の比較・重み付け動作において第２の重み＝−０．８が与えられる
ことを特徴とする、クリーン・アップすべきブロックを決定する方法。
【請求項６】
請求項１記載の方法において、
前記第１の比較・重み付け動作において与えられる第１の重みと、前記第２の比較・重み付け動作において与えられる第２の重みとの選定は、含まれる無効セクタの数が多い方のブロックがクリーン・アップ対象として選択されるように、行われている、
ことを特徴とする、クリーン・アップすべきブロックを決定する方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、コンピュータ・メモリ装置に関し、更に詳しくは、フラッシュ電気的消去可能プログラム可能読出し専用メモリ（フラッシュＥＥＰＲＯＭ）アレイの様々な部分で行なわれる消去・書込み（スイッチング）動作の回数を等しくする方法に関する。
【０００２】
【従来の技術】
最近のコンピュータ・システムでは、長期メモリが幅広く使用されている。代表的には、このメモリは、１つまたは複数のハード・ディスクから成る。ハード・ディスクは、中心軸の回りを高速回転するように固定された１つまたは複数の平坦な円形ディスクを含んでいる電気機械式装置である。平坦なディスクのそれぞれは、何らかの磁気材料でコートされた表裏の面を有している。電気信号により駆動される機械アームは、ディスク上の適所に対しての書込みや読出しを行うよう、各ディスクの各面に磁気ヘッドを位置決めする。それら位置はセクタ上にあり、複数（たとえば、１７個）のセクタで、ディスク片方面における１つの完全なトラックを成している。各セクタは、一定数のバイト（代表的には５１２バイト）のデータを記憶することができる。フォーマットにしたがって、ディスクの一方の面は６００個以上のトラックを有している。今日のパーソナル・コンピュータにおいて使用されている代表的なディスク・ドライブは、４０メガバイトのデータを記憶することができる。
【０００３】
このようなハード・ディスク・ドライブは、非常に有用で、パーソナル・コンピュータの操作にほとんど欠かせない。しかし、このような電気機械式ドライブには欠点がある。このようなドライブは比較的重いので、コンピュータ、特にポータブル・コンピュータの重量をかなり増すことになる。また、サイズも比較的大きいので、コンピュータにおいてかなりの空間を必要とする。しかも、使用の際、かなりの電力を必要とし、ポータブル・コンピュータにおいてはかなりのバッテリ電力を消費する。さらに重要なことは、電気機械式ハード・ディスク・ドライブは衝撃に対し非常に敏感なことである。ポータブル・コンピュータを落下させた場合、そのハード・ドライブの機能が停止することもあり得、これによりデータが壊滅的に失われる可能性がある。
【０００４】
最近、電気機械式ハード・ディスクとは異なる長期記憶の装置が、コンピュータにおいて使用できるようになってきた。その１つに、フラッシュＥＥＰＲＯＭがある。フラッシュＥＥＰＲＯＭメモリは、行・列のメモリ・セルに配列された極めて多数の浮遊ゲート電界効果形トランジスタを有しており、各セルをアクセスし、そのセルのメモリ・トランジスタを、２つのメモリ状態の一方にセットする回路も備えている。フラッシュ・メモリ・セルは、ＤＲＡＭメモリとは異なって典型的なＥＰＲＯＭのように、電力を取り去っても情報を保持している。フラッシュＥＥＰＲＯＭメモリは、長期メモリとして使用するのに適した数多くの特性を有している。たとえば、軽量で、ほんのわずかな空間しか必要なく、電気機械式ディスク・ドライブよりも消費電力が低い。さらに重要なことは、極めて丈夫なことである。典型的な電気機械式ハード・ディスク・ドライブであれば１回の落下でも破壊されてしまうであろうが、そのような落下を繰返しても、悪影響を受けることがない。
【０００５】
しかし、フラッシュＥＥＰＲＯＭにおける問題は、消去をしないと再プログラムできないという点にある。フラッシュＥＥＰＲＯＭは、メモリに用いられている全トランジスタ（セル）のソース端子に高電圧を同時に与えることによって消去される。しかし、これらのソース端子はアレイにおいて金属バスにより相互に接続されているので、全アレイを一度に消去しなければならない。電気機械式ハード・ディスクは、ディスクの第１領域に情報を記憶し、その後、情報の変化時には、ディスクのその同じ領域を再書込みをするが、フラッシュ・メモリ・アレイの場合には、無効（ｉｎｖａｌｉｄ）情報すなわちダーティ（ｄｉｒｔｙ）情報とともにアレイに残っている有効（ｖａｌｉｄ）情報の全てが消去されてしまう。１つのエントリの再書込みの度に全情報が消去されるならば、消去された全ての有効情報も、更新の度に再書込みしなければならない。データ変更にともなってエントリを更新するのに、このようなプロセスを使用した場合には、電気機械式ハード・ディスクの代りにフラッシュ・メモリを用いているコンピュータ・システムの動作は、相当にスローになる。さらに、有効情報の再書込みを要することもあって、フラッシュＥＥＰＲＯＭの消去プロセスは極めて遅く、代表的には１〜２秒かかる。このような消去時間が、高速で変化するデータに対してフラッシュＥＥＰＲＯＭを使用することを妨げていると考えられる。
【０００６】
電気機械式ハード・ディスクにより記憶される情報の場合のように高速で変更するデータのための長期記憶装置としてフラッシュＥＥＰＲＯＭを使用する場合には、電気機械式ハード・ディスクで通常使用されているものではない、システムの動作を遅らせることのない、フラッシュ・アレイを消去および再書込みを行なう方法が必要とされている。
【０００７】
フラッシュ・アレイを、チップ・レイアウトの際に、一緒に消去するセルのグループ（ブロック）に物理的に分離しておくことによって、フラッシュ・メモリの一度に消去する量を減少できることがわかっている。このやり方はある程度まで再プログラミングの苦労を減少できるが、ブロックを別々にフラッシュ消去できるようにするため、セルの各ブロックをシリコン上で物理的に分離しなければならないので、限られた方法でしか使用することができない。なお、必要とされる物理的分離のために、フラッシュ・メモリのそのようなブロックを保持するのに要する領域が増加してしまう。
【０００８】
たとえば、フラッシュ・メモリを、分離されたブロックに分割した新しい装置は、本願の出願人に譲渡され、同日出願された、発明者エス・ウェルスによる米国特許願「半導体メモリ・ディスクに関する方法および回路」に示されている。この装置において、代表的な長期記憶アレイは、一連のブロックに配列されたフラッシュ・メモリから成っている。実施例では、アレイは多くのシリコン・チップに分割され、それぞれのチップは１６個のサブブロックに再分されている。各サブブロックは、別のシリコン・チップ上のサブブロックと物理的に対にされ、奇数のデータ・バイトが一方のチップのサブブロックに記憶され、偶数のデータ・バイトが他方のチップのサブブロックに記憶されるよう、アレイの論理ブロックを形成している。フラッシュ・メモリの各論理ブロックは、他の全ての同様の論理ブロックとは個別に消去できる。しかし、アレイの各論理ブロックは、電気機械式ハード・ディスク・ドライブのトラックに通常に記憶される２５６セクタの情報を保持するのに十分な１２８キロバイトのデータを保持する。したがって、１チップ当り１６個の各々消去可能なサブブロックを備えた３０チップのフラッシュ・アレイは、３０メガバイトの電気機械式ハード・ディスクとほぼ同じ量のデータを保持する。２４０個の各々消去可能な部分（論理ブロック）にデータを分割したとしても、１ブロックの消去は、非常に沢山の情報を消去することになるので、その沢山の情報の全データの消去後に、セクタ毎の再書込みで正しいデータに置き換えることは実際に不可能である。
【０００９】
このような問題の解決のために、データは、フラッシュ・メモリ・アレイのまだ使用可能なスペースが残っているブロックのいずれかに書込まれる。このようにして、データは、ブロック上の物理アドレスまたはデータのセクタ・アドレスに関係なく、アレイの空き位置に書込まれる。たとえば、セクタ５に書込まれるべきデータの一部は、ブロックの次の使用可能な空間（スペース）に、それがどこであろうと、書込まれ、ルックアップ・テーブル（参照用テーブル）には、論理アドレスの、ブロック上の物理位置（セクタ５）を記録される。アレイのこの構成により、第１ブロックにセクタごとに書込めるようになり、第２ブロックにも同様の順次操作で書込め、以下同じように書込めるようになる。セクタのデータに変更がありセクタを再書込みする必要が生じると、データは新しい物理位置に書込まれ、ルックアップ・テーブルのデータが、論理セクタ番号に対しての新しい物理位置を記録するよう変更され、データが書込まれていた最初の物理位置はダーティ（無効）とマークされ、その物理位置を読出そうとするとエラー信号が発生される。ある期間後、ブロックの相当数が一杯になると、特にダーティなブロックからその中の有効な情報を他のブロックへと移し、有効な情報が読出された後のブロック全体を消去することにより、空間を解放することが望まれる。これは、「ブロックのクリーン・アップ」と呼ばれ、消去されたブロック中でそれまでにダーティとマークされていたセクタの全数に等しい数のセクタが開放されるという効果がある。
【００１０】
この構成での特別な利点は、ブロックのを消去を、バックグラウンドで行えることである。すなわち、各無効エントリは、再書込みをする時には消去されず、アレイの機能が読出しおよび書込みのために占有されていない時に、消去されるようにすることができることである。このようにして、外部のホストは、フラッシュ・アレイに書込んだりまたフラッシュ・アレイからの情報を受け取るに際して、たとえ消去に１〜２秒要しても、消去が行なわれていることをほとんど認識しなくてすむ。
【００１１】
他の利点は、フラッシュ・メモリの各ブロックが、電気機械式ハード・ディスクにより記憶される一定の大きさのセクタではなく、物理領域に任意の大きさのデータのセクタを記憶できることである。これにより、一定の大きさのセクタを備えたハードおよびフロッピ・ディスクに特有な、スペース（空間）のロスをほとんどなくすことができる。なぜならば、フラッシュ・メモリのブロックに置かれるにデータのセクタそれぞれが、データを記憶するのに要する空間と同じ長さを必要とするだけだからである。したがって、セクタは、直前のセクタの最後の有効バイトに、セクタ相互間のブランクのスペース（平均では１データ・バイト）を挟んで接するよう、フラッシュ・メモリのブロックに配置できる。データが圧縮されると、５１２バイト・セクタの非圧縮データを記憶するのに要する空間よりもかなり少ない空間に記憶できる。一定の物理的寸法のセクタの最後に通常残される空間は、データが圧縮される場合には排除できる。上記のような構成の他の特性とこのような無駄な記憶空間の排除とにより、圧縮率１．５のデータを記憶するフラッシュ・メモリは、所与の大きさの代表的な電気機械式ハード・ディスクにより記憶されるデータと同じ量のデータを約四分の三の物理的記憶空間で記憶することができる。
【００１２】
【発明が解決しようとする課題】
フラッシュ・メモリにおける問題点には、使用できる寿命が制限されていることがある。これは、消去・書込み（スイッチング）動作を繰り返すと、アレイの浮遊ゲート・トランジスタのスイッチング動作に要する時間が長くなるためと思われる。そのような繰り返しの回数はかなり大きな数ではある。約１０，０００回の消去・書込み動作の後に、消去・書込み動作が遅くなり始めたとして、消去・書込み動作の長期化がシステム・オペレーションに何らかの影響を与えるようになるのは、約１００，０００回の消去・書込み動作を行った後であると見積られてきた。たとえそうでも、データを記憶するセルを選択するための代表的なプロセスでは、ブロック上のあるトランジスタ群およびあるトランジスタのブロック群は、他のトランジスタよりも一層頻繁に消去・書込み動作をさせられる傾向がある。アプリケーション・プログラムが記憶されているブロックのようなフラッシュ・メモリ・アレイのある領域は、めったに再書込みを受けないということがわかっている。一方、アプリケーション・プログラムにより特定の演算のためデータが蓄積されるブロックは、非常に頻繁に変更され従って再書込みされなければならない。さらに、すぐに変更されるデータを記憶するブロックは他のブロックよりも多くのダーティ・セクタを有しているので、これらブロックはより頻繁にクリーン・アップされることになる。一旦、ブロックは、動作中にクリーン・アップされると、あまり変更されないデータを受けよりも、頻繁に変更されるデータを受け取ることの方がはるかに多いであろう。したがって、迅速に変更されるデータを最初に含んでいるブロックは、データ・アーキテクチャの特性により、自動的に、頻繁に変更されるデータを更に受けることになる。データ変更は、そのようなブロックのクリーン・アップを要求することになる。したがって、アレイ全体における消去・書込みの回数を等しくするために何も行なわなかった場合、特定のブロックが、他のブロックよりもかなり速く故障することになる。
【００１３】
このため、フラッシュ・メモリの各ブロックの消去・書込みのサイクルの回数を制御する手段が大変に要求されている。そのような手段は、フラッシュ・メモリ・アレイのある部分が早期に故障することにつながってしまう統計学的むらを修正するのに、大いに効果があるであろう。本発明の目的は、フラッシュ・メモリ・アレイの寿命を大幅に延長する方法を提供することである。本発明の他の目的は、フラッシュ・メモリ・アレイの様々な部分での消去・書込みが等しく生じるようにする方法を提供することである。
【００１４】
【課題を解決するための手段】
上記の目的は、本発明による、メモリ・セル・ブロックに分割されており、ブロック毎に消去可能であるフラッシュＥＥＰＲＯＭアレイのクリーン・アップにおいて、全ての有効データをアレイの他のブロックに書込み、それから、そのブロック全体を消去して、フラッシュＥＥＰＲＯＭアレイクリーン・アップする方法において、各ブロックに含まれる無効セクタの数と、各ブロックが受けた消去・書込み動作の数との比較に基いて、クリーン・アップするブロックを決定する過程を有することを特徴とするフラッシュＥＥＰＲＯＭアレイをクリーン・アップする方法により、解決される。
【００１５】
【実施例】
以下の詳細な説明において、コンピュータ・メモリにおけるデータ・ビットの操作をアルゴリズムおよび記号表示によって示している部分がある。これらのアルゴリズム記述や表示は、当業者に技術の内容を最も有効的に伝えるため、データ処理の分野における当業者が用いている方法である。ここでは、また一般にも、アルゴリズムは、目標結果に至る過程のシーケンスであると考えられる。これらの過程は物理量の物理操作を要する過程である。一般に、必ずしも必要ではないが、これらの量は、記憶、転送、結合、比較または操作可能な電気または磁気信号の形態である。これらの信号を、ビット、数値、エレメント、記号、文字、語句、数などで呼称することが、主に共通使用のため、時に便利であることがわかっている。しかし、これらおよび同様の語句は、いずれも、適切な物理量に関連しかつこれら量に用いられる便利な単なる名称であることに留意されるべきである。
【００１６】
さらに、実行される操作は、一般に、ヒューマン・オペレータにより実行されるメンタル・オペレーションに関連した、たとえば、加算または比較のような言葉で呼ばれることがある。本発明の一部を成しているここで述べられているオペレーションのいずれにおいても、大抵の場合、ヒューマン・オペレータのこのような能力は必要でもまたは要求されてもいない。オペレーションはマシン・オペレーションである。いずれの場合も、コンピュータまたはその一部を操作する方法オペレーションと計算方法自体との間の相違を心に留めておかなければならない。本発明は、電気または他の（たとえば、機械的、化学的）物理信号を、他の目標物理信号を発生するよう処理する際のコンピュータを操作する装置および方法に関する。
【００１７】
図１は、本発明が実施されるフラッシュＥＥＰＲＯＭメモリ・アレイ１０をブロックで示す。アレイ１０は、フラッシュＥＥＰＲＯＭメモリの複数のブロックＢ０〜Ｂ１５を含む。各ブロックは、行および列に配列された浮遊ゲート電界効果形トランジスタ・メモリ・セル（図示せず）を含んでいる。これらのメモリ・セルは、メモリの特定のブロックおよびそのブロックの特定の行および列を選択するための回路を有しているので、特定の位置におけるメモリ・セルを読出したりまたは書込みを行なうことができる。トランジスタ・メモリ・アレイおよびそれに関連したアクセス回路の詳細は、当業者には周知であるので、ここでは省略する。
【００１８】
多くの出版物に示されているように、フラッシュ・メモリは、基本的にはＥＰＲＯＭアレイであり、それの全メモリ・トランジスタのソース端子に同時に高電圧値を与えることにより全アレイを消去できる機能を備えたものである。このような消去により、各セルは１の状態になる。その状態の時に、ゼロまたは１をセルに書込むことができる。１はセルを同じ１の状態のままにし、一方、ゼロはセルを１状態からゼロ状態にスイッチングをさせる。セルは、消去に必要とされる高い電圧値（代表的には、１２ボルト）をソース端子に供給されなければ、ゼロ状態から１の状態へとこれと逆のスイッチングをすることはない。１つのブロックにおけるメモリ・トランジスタの全ソース端子は相互に結合されているので、ゼロ状態のセルは、アレイの全ブロックが再び消去されるまで、その状態のままである。
【００１９】
図１に示されたアレイ１０において、メモリのブロックＢ０〜Ｂ１５は、アレイ１０の第１チップ１１に配置されている。別の（たとえば３０個の）シリコン・チップ１１は、アレイ１０の他のブロックをそれぞれ保持し、実施例では合計２４０のブロックを与える。実施例では、前述したように、各ブロックは、隣接するチップに位置する一対のサブブロックから構成されている。サブブロックは、入力と出力を有し、奇数のデータ・バイトを一方のサブブロックに記憶させ且つ偶数のデータ・バイトを他方のサブブロックに記憶させるための選択導体をさらに有している。このことから、ブロックは、一対のサブブロックを含んでいると考えることができる。
【００２０】
ホストが、アレイに記憶すべきデータ（たとえば、アプリケーション・プログラム）について、完全に消去されたアレイのいずれかのブロックに対して、その書込みを開始する際、記憶すべきデータは、ブロックに、それがデータで一杯になるまで、セクタからセクタへと順次に書込まれる。そして、書込みは、空きの空間を有する次のブロックに進む。書込みが完了した後は、いずれの時点においても、データが記憶されたブロックおよびセクタを問合せることにより、情報をアレイ１０から読出すことができる。
【００２１】
上記の構成において、データは、セクタの寸法が任意で良い（後述する）ことを除き、従来技術の電気機械式ハード・ディスクにデータを記憶するのに使用される物理セクタと同様のセクタに記憶される。アレイのセクタに記憶されたデータが変更されて、そのセクタに既に書込まれた情報を変更すべき時には、新しい変更後の情報は、アレイ１０の空き空間を有するブロックのいずれかに位置する新しいセクタに書込まれ、古いセクタは無効（ダーティ、Ｄｉｒｔｙ）とマークされる。古い情報に上書きするのではなく、このように行うのは、古い情報を含むブロックの全てが消去されて初めて、古い情報を再書込みできるからである。有効なデータを破壊することなく全ブロックを消去するには、有効（Ｖａｌｉｄ）なデータの全てをアレイ１０の他のブロックにコピーし、元のブロックを消去し、有効なデータを元のブロックに再書込みし、その後、元のブロックのダーティ・データが書込まれていたところに新しいデータを書込まなければならなかった。しかし、これは非常に時間がかかる作業であるので、各エントリの再書込みのためのこのようなプロセスを用いると、コンピュータの動作は遅くなり、動作停止といえるほどになる。したがって、これは実用的ではない。その代わりに、新しい情報を、別の空いているブロック（たとえば、ブロックＢ７）の新しい位置に書込み、古い位置は、エントリのセクタ番号とともに無効を示すゼロを書込むことにより、ダーティとマークされる。アレイのブロックを消去することなく、ゼロの値をいずれのメモリ・セルにも書込めることは認識されよう。
【００２２】
この構成では、データが置き換えられるので、データがどこに記憶されているかを示すのに使用されるセクタ番号には、物理セクタ番号ではなく論理セクタ番号が用いられる。この点は、電気機械式ハード・ディスクでデータを配置するのに物理セクタ番号が使用されているのとは対照的である。論理セクタ番号を使用できるようにするため、アレイ１０とともに用いられるランダム・アクセス・メモリ１６に、物理セクタ番号と対比して論理セクタ番号を表にしたルックアップ・テーブル１７が記憶されている。このテーブル１７は、特定の論理セクタが存在する、アレイ１０中の物理的位置を、決定するのに使用される。
【００２３】
データが置き換えられる、このような構成では、しばらくすると、アレイの各ブロックは、ダーティとマークされて記憶には使用できない多くのエントリを、有することになる。その結果、アレイ１０がデータで一杯になると、新しい情報を記憶するための空間を作るため、ブロックからダーティ情報をクリアしなけらばならなくなる。本発明の一実施例では、このクリアは、ダーティな空間の合計量が、ダーティ空間と空き空間の全合計の８０％になった時に行なわれる。典型的には、アレイ１０の最もダーティなブロックが消去べきものとして選択される。これにより、消去対象のブロックからアレイの別のブロックに移動する有効なデータの量を最少にすることができる。有効な情報が別のブロックに書込まれ、新しいアドレスがルックアップ・テーブル１７に記録されると、情報を読出し終えたブロックは消去される。その後、消去されたブロックは、全くきれいなブロックとして動作に復帰する。このクリーン・アップ操作を行えるようにしておくために、ブロックのいくつかを、クリーン・アップの必要時のために確保しておかなければならない。本発明を用いた装置の一例では、使用可能な２４０のブロックのうちの１４のブロックを使用して、書込み動作の継続のため、および、クリーン・アップ動作のために十分な空間を提供する。
【００２４】
図２には、前述した利点を得るため個々のブロックで使用される論理構成が示されている。図２は、アレイ１０の各ブロックにデータを記憶する方法を理解するのに有効な理想化した図である。図２では、代表的なブロックを方形で示している。この方形領域は、各ブロックにより与えられる１２８Ｋバイトの記憶用に配列された複数のトランジスタ・ディバイスを含んでいる。前述したように、個々のブロックの領域は、実際には、２つの物理チップそれぞれのサブブロックに分けられ、一方のチップのサブブロックは奇数のデータ・バイトを保持し、他方のチップのサブブロックは偶数のデータ・バイトを保持する。トランジスタ・メモリ・ディバイス、ブロックを操作する線、行および列の選択線は、図示されていないが、フラッシュ・メモリを設計する当業者には周知である。
【００２５】
図２に示すように、データは、上と下から開始するブロック２０に記憶される（ブロックの一番下の狭い領域２１は、ブロック構造データのために確保される）。ブロック２０の上部の、セクタ変換テーブル（ヘッダ）と呼ばれる識別フィールドには、データのアドレスとしてオペレーティング・システムにより用いられる論理セクタ番号が記憶される。たとえば、第１セクタ番号５８１１２は、上部の第１エントリのためのヘッダに記憶される。セクタ番号に続いて、様々な属性ビットおよびポインタ値が記憶される。一実施例に含まれている属性には、エントリの妥当性（Ｖ）の表示、校正番号（Ｒｅｖ＃）、データが圧縮されているかどうかの表示、エントリがデータを含んでいる（ＷＤ）か否（ＷＯＤ）かを示すビットがある。エントリの妥当性（Ｖ）の表示は、１ならば有効を意味し、ゼロならば無効を意味する少なくとも１つのビットであり、このビットは、正しい妥当性を確実に記憶しておくめに二重にしておくことができる。校正番号（Ｒｅｖ＃）は４ビットの番号である。エントリがデータを含んでいる（ＷＤ）か否（ＷＯＤ）かを示すビットが使用されているので、セクタをデータなしに作ることができる。
【００２６】
ポインタ値（ブロックへのオフセット）は、ブロック２０のデータ領域において論理セクタ（例えば５８１１２）のデータが記憶されている物理アドレスを示す。図２の左側の矢印は、論理セクタ（例えば５８１１２）のデータの第１ビットが記憶されている物理位置を示している。記憶されるべきデータは、その量が書込み動作の時点では知れているので、ブロック２０の実施例において、データは、それまでに記憶されたデータの次に書込むことにより記憶される。ブロック２０の第１セクタである論理セクタ５８１１２の場合、データは、セクタ番号５８１１２に関するポインタとして記憶されたアドレスの最初から、データ領域の始まり（最下部）まで書込まれる。最下部でデータが始まる位置は、ブロックの上部における第１ヘッダ・エントリの前に記憶された開始ポインタ値によりマークされる。ブロックにおけるこれらの２つの位置は、ブロック２０の左上の隅から左下の隅まで延びている矢印により結合されて示されている。
【００２７】
論理セクタ５８１１２に書込まれるデータの量は、固定されておらず、変更できる。しかし、コンピュータ・システムと記憶装置との間の代表的なインタフェイスでは、データは、５１２バイトのセクタに記憶するよう割当てられる。図２には、第２論理セクタ５と、ブロック２０においてその論理セクタ５のデータの第１ビットを記憶する物理位置に向けられたポインタも模式的に示されている。セクタ５のデータは、その最後の行がセクタ５８１１２のデータの第１行のすぐ上の行に位置するよう、書き込み済みの最新のデータ・セクタ（セクタ５８１１２）のすぐ上で開始しして下方へ延びるデータ領域に記憶される。新しいセクタのデータは、最後に書込まれたセクタのデータのすぐ上のすべての行に書込まれるので、このブロック記憶構成において無駄になるデータ空間の量はほんのわずかである（平均１バイト）。記憶のために供給されるデータが圧縮されていれば、固定のセクタ・サイズの記憶装置において、通常、空のままにされる記憶空間の量は無視できる。これは、固定のセクタ・サイズを用いている外見上一杯になった電気機械式ハード・ディスクに代表される大量の未使用空間とは著しく対照的である。
【００２８】
前述したように、セクタ番号の物理位置は、チップ番号、ブロック、データ検索に関する他情報（たとえば、行および列アドレス）とともに、ルックアップ・テーブル１７（これは、アレイ１０の他の構成要素を保持している回路板のスタティック・ランダム・アクセス・メモリに保持されているのが望ましい）に記憶されている。ブロック２０のいずれかのセクタに記憶されたデータは、次のようにして検索できる。すなわち、ルックアップ・テーブル１７からセクタ番号の物理アドレスを決定し、そのアドレスを用いてセクタ番号が記憶されたブロック２０の物理位置を見つけ、そして、データの開始位置のポインタと、検索されるセクタ番号のすぐ上に記憶されているセクタ番号を有するセクタの開始位置のポインタと（これら２つの値は、データを探しているセクタの開始および終了位置を決定する。）を、検索することにより、検索できる。
【００２９】
フラッシュ・メモリ・アレイにより使用される、データの再書き込みを行なう一般的でない装置では、メモリ割当てシステムが、書込みおよび再書込みされるデータ用に使用可能であるよう、メモリを継続的に新しくするすなわち新たに消去する必要がある。前述したように、これには、無効データを保持しているブロックをクリーン・アップして、そのダーティ・セクタを解放するため、ブロックのいくつかを常に利用できるようにしておくことが必要である。
【００３０】
いずれのメモリ・アレイの操作においても生じる問題点は、そのメモリの読出し、書込みおよび消去しようとする時、時々失敗があることである。フラッシュ・メモリにおいて非常に重大な問題は、長期間使用した後、メモリ・トランジスタが、規定された期間内での消去・書込み能力を失うことである。この能力損耗は、実際には、信号がメモリ・セルから読出されて最終値に整定するまでに必要な時間が延びることが分った。データをセルに正しく記憶し、セルから読出すことはできるが、それに要する時間が長くなり、回路に要する規定の範囲内にはない。フラッシュ・メモリがこの症状を呈し始めると、整定時間が長くなり始め、結局、メモリは有用な範囲を超えてしまう。図４は、行なわれた消去・書込み動作の回数に対する、出力信号の整定時間をとった、フラッシュ・メモリ・アレイの代表的な使用特性を示している。図示のように、消去・書込み動作が約１０，０００回を超えると、フラッシュ・メモリのブロックの整定時間は長くなり始める。この１０，０００回という消去・書込み動作の回数が、このようなアレイにおける代表的な寿命として選択されている。
【００３１】
前述したように、アレイのダーティ・セクタにより占められている記憶空間を解放する必要がある場合に、最もダーティなブロックをクリーン・アップするようにするものとすると、あるブロックの使用が、アレイの他のブロックよりも多くなることになろう。そうなるのは、あるブロックが、他のブロックに記憶されたデータよりも頻繁に変更されるデータを、最初に受け取るからである。たとえば、アプリケーション・プログラムは、典型的には使用中には変更されないが、アプリケーション・プログラムにより使用されるデータはしばしば変更される。頻繁に変更されるデータを受け取るブロックは、アレイの他のブロックよりも速くクリーン・アップされる。一旦、クリーン・アップされると、これらブロックは、おそらく、別のすぐに変更するデータを受け取ることになる。なぜならば、スタティック・データを含んでいるアプリケーション・プログラムは記憶済みであり、頻繁に変更されるデータは、通常、長期記憶装置に書込まれるタイプのデータであるからである。結局、これらブロックは、さらにクリーン・アップを受けることになろう。
【００３２】
その結果は、あるブロックは、他のブロックよりもかなり頻繁に使用されることになり、他のブロックよりかなり頻繁にクリーン・アップされる、ということになろう。比較的短い期間では、頻繁に変更されるデータを記憶する、僅かなブロックが、消去・書込み動作の通常の寿命に至るだけで、多くのブロックはそれ程使用されない。わずかな数のブロックが著しく使用されて故障しても、アレイ全体の故障となるので、アレイを機能させるためには、多くのブロックが常にクリーン・アップの対象とするようにしておく必要がある。
【００３３】
本発明の動作を可能にするため、ブロックが消去された回数のカウントが、他のデータから離れている、ブロック中の小さなブロック状態部分２１に、保持される。この部分２１は、図２おいて、ブロック２０の下の方に示されている。
【００３４】
フラッシュ・メモリ・アレイにおける消去・書込み動作の回数を均等化するため、本発明のプロセスは使用される。代表的には、必要的ではないが、このプロセスは、制御回路１４のマイクロプロセッサにより実行されるソフトウェア・プロセスであり、その制御回路１４は、そのソフトウェアとともに読出し専用メモリに記憶されている命令を使用する。図３は、フラッシュ・メモリ・アレイのブロック間で消去・書込み動作の回数を均等化するために実行される多くのオペレーションを示す図である。この図は、状態図の形式で示されているが、実際には操作のフローチャートに等しい。オペレーションは、読出し／書込み／消去の制御回路１４の読出し専用メモリに記憶されたソフトウェアにより制御される。本発明の説明のため、読出し／書込みの制御回路１４は、上記マイクロプロセッサおよび読出し専用メモリの他に、コマンド状態マシンおよび書込み状態マシンを含んでいると考えられる。これらのマシンは、読出し、書込み、消去のためのアレイ・チップのインタフェイスを形成する。この回路は、本願の出願人に譲渡され、１９９１年２月１１日に出願された、発明者フランドリッチ他による米国特許願第０７／６５５，６４３号「コマンド状態マシン」と、本願の出願人に譲渡され、１９９１年２月１１日に出願された、発明者キネット他による米国特許願第０７／６５４，３７４号「不揮発性半導体メモリのプログラムおよび消去をする回路および方法」とに述べられている。一実施例では、コマンド状態マシンと書込み状態マシンは、物理的には、各チップ１１の一部である。
【００３５】
オペレーションは第１のステップ３０から始まる。第１のステップ３０では、クリーン・アップ操作が必要かどうかの決定のための評価が行なわれる。クリーン・アップが必要かどうかは、情報を書込みまたは再書込みするために利用できる空間がブロックにあるかどうかの問題に基く。一実施例では、フラッシュ・メモリの全アレイ（使用中の有効セクタをまない）の８０％以上がダーティである場合、使用できる空間は十分でないと考えられ、クリーン・アップ操作を行なう必要がある。この決定は、アレイ１０に関連したスタティックＲＡＭ１６における、小規模データ・ベース１２に空きスペース量を、小規模データ・ベース１３にダーティ空間の量を保持することによって行なわれる。データ・ベース１３は各ブロックにおけるダーティ空間の量と全ダーティ空間をリストし、一方、第２データ・ベース１２は各ブロックにおける空き空間の量とアレイにおける全空き空間をリストする。セクタがダーティであるとマークされる度に、そのセクタのサイズが、全ダーティ空間に加えられる。クリーンな未使用（空き）セクタが、書込みのために割当てられる度に、そのサイズが空き空間の全量から減算される。ブロックが不良であるとマークされる度に、そのブロックから全ユーザ・データが他にコピーされる。したがって、不良ブロックにおける空き空間の量は、空き空間の総量から減算され、不良ブロックにおけるダーティ空間の量は、ダーティ空間の量から減算される。データ・ベース１２，１３は、読出し／書込み／消去制御回路１４のプロセッサにより、その読出し専用メモリに記憶されたソフトウェアを用いて保持される。データ・ベースをルーチンとして保持することにより、ダーティと空きの合計の空間に対するダーティ空間の比率は、ダーティである残りのアレイ空間のパーセンテージの有効な尺度として常に使用できる。十分な空き空間がある場合、クリーン・アップは必要とされない。しかし、十分な空き空間がない場合には、クリーン・アップが必要になる。
【００３６】
クリーン・アップが必要であるとわかると、プログラムは、クリーン・アップに最も適したブロックを選択するステップ３１に移動する。決定は、一組の基準に基いて行なわれる。
最初の基準は、どのブロックが最もダーティであるかということである。最もダーティなブロックの決定は、データ・ベース１３に保持されている各ブロックに関するダーティ空間の量（すなわちダーティ・セクタの数）を、データ・ベース１３に保持されている他の各ブロックのダーティ空間（すなわちダーティ・セクタの数）に比較することによって行なわれる。
２番目の基準は、どのブロックが最も少ない回数のクリーン・アップ操作（サイクル）を経過したかということである。どのブロックが最も少ない回数のクリーン・アップ操作を経過したかの決定は、各ブロックの下に示された固定ブロック構造領域に記憶された値を考察することにより行なわれる。示されているように、この領域は、ブロックが何回クリーン・アップ操作を経過したかを実質的に示す値（消去された回数のカウント（段落００３３参照））を含んでいる。この評価には他の要因も含められるだろうが、本発明の目的に関しては意味がないので本明細書での検討は省略する。
【００３７】
上記の最初の基準に関して更に説明をすると、各ブロックにおいて、ダーティ・セクタの数を調査することにより決定された値は、倍率（一実施例では８０％）の重みを付けられる。このように、各ブロックについて、それに含まれるダーティ・セクタ（すなわち無効セクタ）の数を全ての他のブロックに含まれる無効セクタの数と比較しその比較により得られる値に重みがつけられる。
一方、上記の２番目の基準に関して更に説明をすると、クリーン・アップ操作の数は、（最も多くのサイクルを経験したブロックと、当該のブロックとに関するクリーン・アップ操作回数の差を見いだすことにより）他の倍率（同実施例では２０％）の重みを付けられる。このように、各ブロックについて、それの受けた（クリーンアップ回数を実質的に示す）消去回数と、最も多くの消去を受けたブロックの消去回数との差を求めそれにより得られる値に重みがつけられる。
そして、これらの２つの結果は合計され、最も高い値を持つブロックがクリーン・アップのため選択される。クリーン・アップされるブロックの選択には、最もダーティなブロックの値が圧倒的な影響を持つが、２つのブロックがほぼ等しくダーティな場合には、最も少なく消去・書込みのサイクルを経験したブロックが選択される。このことは、少ない消去・書込み動作のブロックをクリーン・アップのために選択する効果がある。これは、最も頻繁に変更されると思われるデータが、クリーン・アップ後に書込まれるであろうブロックを選択するという最終的効果を有している。全体的な効果は、ブロックにおける消去・書込み動作が均等化され始めるということである。
【００３８】
クリーン・アップに適したブロックが選択されると、プロセスは、他のブロックにおける使用し得る空きセクタ空間を見つけるステップ３２に移動する。有効なセクタを記憶する空間が発見されると、プロセスは、ステップ３３に移り、クリーン・アップ対象のブロックのセクタから有効なデータを使用可能な空間に書込む。図３は、使用可能な空間に有効なデータを書込む、２０回繰り返されるプロセスを示している。これが生じるのは、現在使用されている本発明の一実施例においては、ホストにより要求されたオペレーションを遂行できるよう、クリーン・アップの種々のステップが割り込み可能であることが必要とされるからである。
【００３９】
したがって、プロセスの様々なステップは論理部分に分割され、それぞれの部分は、５００マイクロ秒で行なわれる。このように、図示されたプログラムは、プロセスの各論理ブロックの間で、ホストのオペレーションにより割り込み可能である。クリーン・アップ操作の（たとえば、他のブロックの使用可能なセクタ空間への有効なセクタの書込みのような）長い部分は、全オペレーションが終わるまで、各５００マイクロ秒が割込まれる。
【００４０】
クリーン・アップ対象のブロックのセクタにおける有効なデータを他のブロックのセクタへの書込むことが完了すると、プログラムは、アレイが保有する様々なデータ・ベースを更新するステップ３４に移動する。これには、次が含まれている。すなわち、各ブロックの上部にあって、書込み操作により影響されて古いヘッダが無効にされているセクタ変換テーブル（ヘッダ）を更新すること、フラッシュ・メモリに関連し、論理セクタをメモリのいずれかに配置させる、ＳＲＡＭ中のルックアップ・テーブル１７を、新しい物理アドレスで更新すること、ダーティおよび空き空間の量をリストする、ＳＲＡＭに保持されたデータ・ベース１２，１３を更新すること、が含まれている。
【００４１】
データ・ベースが更新された後、有効なデータを含んでいるセクタの書込みが継続され、クリーン・アップされるブロックにおける全ての有効なセクタが他のブロックに移動し終わるまでループされる。ヘッダ部分にクリーン・セクタを含まないブロックにより示されるようにこれが完了すると、プログラムはステップ３５に移動する。ステップ３５では、ブロックの消去プロセスが開始される。消去プロセスは典型的に１〜２秒で行なわれるので、消去のための待機を示している次のステップは、一実施例ではその期間中各５００マイクロ秒で消去プロセスが割り込まれ得ることを示している。
【００４２】
消去操作が行なわれたら、プログラムはステップ３７に移動する。このステップ３７において、データ・ベースが再び更新される。これらのデータ・ベースは、クリーン・アップされたブロックが経過したスイッチング動作のカウント（サイクル・カウント）、メモリにおける空き空間およびダーティ空間の量、本発明には関係ない他のデータを含んでいる。
【００４３】
データ・ベースが更新された後、プログラムは、クリーン・アップが必要かどうかの評価を行う最初のステップ３０に戻る。ダーティ・データに占有された記憶域を解放するためクリーン・アップがなお必要ならば、全プロセスが繰り返される。これは、クリーン・アップが必要とされなくなるまで継続される。
クリーン・アップがもう必要でなくなると、プログラムはステップ３８に移動する。ステップ３８において、消去・書込み動作の均等化をする（「消耗レベリング（ｗｅａｒ ｌｅｖｅｌｉｎｇ）」と呼ばれる）必要があるかどうかの決定が行なわれる。この消耗レベリングのかなりの部分は、プロセスの主要部分でクリーン・アップに最適なブロックを選択するステップにおいて、既に行なわれていることは明らかであろう。しかし、そうならない態様でフラッシュ・メモリのプロセッサが動作している時、アレイの様々なブロックにおける消去・書込み動作の総数を近づけるよう、上記のプロセスを用いることが有効であることがわかった。
この目的のため、各ブロックが行なった消去・書込み動作の数を比較することにより評価が行なわれ、アレイの最も多くサイクルされたブロックより５００回少なくクリーン・アップされたブロックがあるかどうかを決定する。このようなブロックが生じていない場合、プログラムはそのプロセスから出る。又、このようなブロックがある場合には、消耗レベリング・クリーン・アップ操作が開始される。このように、利用できる空きをつくるためのクリーン・アップの必要性はないが、クリーン・アップ操作が可能である場合に、受けた消去回数に５００以上の差があるブロックがあると、消耗レベリング・クリーン・アップ操作が開始される。
【００４４】
この時点で消耗レベリング・クリーン・アップを開始するのは、クリーン・アップされたブロックが、頻繁な変更を受け易い新しいデータを受けるであろうと、言う点にある。したがって、プログラムは、クリーン・アップに最適なブロックであるかどうかの評価が消耗レベリングの基準に基いて行なわれるステップ３９に進む。ダーティ・セクタや、行なわれた消去・書込み動作の数など同じファクタについての考察がなされる。しかし、各値に与えられる重みは、消去・書込み動作の数に対してより高い重みが与えられるように変えられる。たとえば、ある実施例では、ダーティ・セクタの数には２０％の重みが付けられ、一方、（最も多くサイクルされるブロックのクリーン・アップ操作と、当該ブロックのクリーン・アップ操作と間における差を見いだすことにより測定される）消去・書込みの数には８０％の重みが付けられる。これらの数は合計され、最高値のブロックがクリーン・アップのために選択される。消去・書込みの数が、クリーン・アップ用のブロックの選択において、圧倒的な影響力を持つことがわかるであろう。消去・書込みの数が少ない程、そのブロックが選択される可能性は高くなる。しかし、同数の消去・書込み回数の２つのブロックがあるとすると、最もダーティなブロックが、最高合計値を有しかつ選択される。
したがって、消耗レベリング・クリーン・アップの一般的な効果は、これまでにクリーン・アップされた回数が最も少ないブロックをクリーン・アップすることである。適切なブロックが消耗レベリング・クリーン・アップ操作のために選択されると、プログラムは、クリーン・アップを開始するステップ３２に移動する。その後は、前述したようにクリーン・アップのため同様のステップをたどる。
【００４５】
本発明について、実施例に基づいて説明したが、本発明の思想から離れることなく様々に改変できることは当業者には明白であろう。
【００４６】
【発明の効果】
本発明のプロセスを用いることにより、ブロック間での使用量が均等化されると同時に、継続的に使用できるメモリのブロックが提供される。これにより、メモリ・アレイの寿命を延ばす効果がもたらされ、通常の動作では寿命は約２８年と算定される。これは代表的なコンピュータ・コンポーネントをはるかに超える寿命である。
【図面の簡単な説明】
【図１】 本発明が用いられるフラッシュ・メモリ・アレイの概要を示したブロック図である。
【図２】 図１に示したようなフラッシュ・メモリ・アレイの１つのブロックにおける情報の記憶パターンを示したブロック図である。
【図３】 フラッシュ・メモリ・アレイにおける消去・書込み動作を均等化する、本発明にしたがった方法の一部を示したフローチャートである。
【図４】 フラッシュ・メモリ・アレイに関する損耗特性を示したグラフである。
【符号の説明】
１０ フラッシュＥＥＰＲＯＭメモリ・アレイ
１４ 読出し／書込み／消去制御回路
１６ ランダム・アクセス・メモリ
１７ ルックアップ・テーブル
２０ ブロック
【図１】
0003641280.tif 000002
【図２】
0003641280.tif 000003
【図３】
0003641280.tif 000004
【図４】
0003641280.tif 000005