(57)【要約】【課題】論理・物理マッピング手法を用いてフラッシュメモリのアクセス時に性能低下を最小限に抑える方法、フラッシュメモリに前記論理・物理マッピングに関する情報を効率よく格納し管理する方法及びそれらの方法を用いたフラッシュメモリを提供する。【解決手段】書き込みたいデータの最も最近に書き込まれた論理ページ番号を有する物理ページに前記書き込みたいデータとオフセットが一致するセクターが空いているかどうかを判断するステップと、前記判断の結果、前記オフセットが一致するセクターが空いていると、前記物理ページの前記オフセットが一致するセクターにデータを書き込むステップと、前記判断の結果、前記オフセットが一致するセクターが空いていないと、空いているた物理ページを選択し、前記データとオフセットが一致するセクターにデータを書き込み、前記選択された空いた物理ページに前記データに対する論理ページ番号を書き込むステップとを含む。【選択図】図７
2005196736.tif 000002
【特許請求の範囲】
【請求項１】
所定数のセクターからなるページを有するブロックを一つ以上有し、前記セクターまたは前記ページ単位でデータを書き込み、前記ブロック単位でデータを消去するフラッシュメモリにデータを書き込む方法において、
書き込みたいデータの最も最近に書き込まれた論理ページ番号を有する物理ページに、前記書き込みたいデータとオフセットが一致するセクターが空いているかどうかを判断する第１のステップと、
前記判断の結果、前記オフセットが一致するセクターが空いていると、前記物理ページの前記オフセットが一致するセクターにデータを書き込む第２のステップと、
前記判断の結果、前記オフセットが一致するセクターが空いていないと、空いている物理ページを選択し、前記データとオフセットが一致するセクターにデータを書き込み、前記選択された空いている物理ページに前記データに対する論理ページ番号を書き込む第３のステップと
を含むことを特徴とするフラッシュメモリにデータを書き込む方法。
【請求項２】
前記データが書き込まれるのは、前記物理ページの主領域であり、前記論理ページ番号が書き込まれるのは、前記物理ページの補助領域であることを特徴とする請求項１に記載のフラッシュメモリにデータを書き込む方法。
【請求項３】
前記第１のステップの前に、前記書き込みたいデータの論理ページ番号が書き込まれたことがあるかを判断し、書き込まれたことがあれば、前記第１のステップを行い、書き込まれたことがなければ、既存の物理・論理マッピング情報に基づいて、予め指定された位置にデータ及びそのデータの論理ページ番号を書き込むステップをさらに含むことを特徴とする請求項１に記載のフラッシュメモリにデータを書き込む方法。
【請求項４】
前記第１のステップは、書き込みたいデータの最も最近に書き込まれた論理ページ番号を有する物理ページに、前記書き込みたいデータとオフセットが一致するセクターが空いているか、及び前記物理ページに前記セクターの次のセクターが全て空いているかを、共に判断することを特徴とする請求項１に記載のフラッシュメモリにデータを書き込む方法。
【請求項５】
前記第３のステップで書き込んだ論理ページ番号を有する既存の有効な論理ページに書き込まれたデータのうち、前記第３のステップで書き込まれたデータ以外のデータを前記選択された空いている物理ページにコピーする第４のステップをさらに含むことを特徴とする請求項１乃至４のいずれかに記載のフラッシュメモリにデータを書き込む方法。
【請求項６】
前記データが上位ページから順次書き込まれる場合に、前記有効な論理ページを検索するのは、１つ以上の同じ論理ページ番号を有する論理ページのうち、最も下位のページを検索することにより行われることを特徴とする請求項５に記載のフラッシュメモリにデータを書き込む方法。
【請求項７】
前記データがインプレース優先方式で書き込まれる場合に、前記有効な論理ページを検索するのは、１つ以上の同じ論理ページ番号を有する論理ページのうち、インプレース位置にあるページを除いたページを選定し、前記選定されたページのうち最も下位のページを検索することにより行われることを特徴とする請求項５に記載のフラッシュメモリにデータを書き込む方法。
【請求項８】
所定数のセクターからなるページを有するブロックを一つ以上有し、前記セクターまたは前記ページ単位でデータを書き込み、前記ブロック単位でデータを消去するフラッシュメモリにデータを書き込む方法において、
書き込みたいデータの最も最近に書き込まれた論理ページ番号を有する物理ページに、前記書き込みたいデータを格納できる空いているセクターが存在するかどうかを判断する第１のステップと、
前記判断の結果、空いているセクターが存在すると、前記物理ページの空いているセクターにデータを書き込み、前記物理ページに前記データに対する論理セクター番号を書き込む第２のステップと、
前記判断の結果、空いているセクターが存在しないと、空いている物理ページを選択し、空いているセクターにデータを書き込み、前記選択された空いている物理ページに前記データに対する論理ページ番号及び論理セクター番号を書き込む第３のステップと
を含むことを特徴とするフラッシュメモリにデータを書き込む方法。
【請求項９】
前記第２のステップ及び前記第３のステップで論理セクター番号を書き込むのは、物理ページの主領域でデータを書き込んだセクターの位置と対応する補助領域での位置に書き込むことを特徴とする請求項８に記載のフラッシュメモリにデータを書き込む方法。
【請求項１０】
前記第３のステップで書き込んだ論理ページ番号を有する既存の有効な論理ページに書き込まれたデータのうち、前記第３のステップで書き込んだデータ以外のデータ、及びそのデータの論理セクター番号を前記選択された空いている物理ページにコピーする第４のステップをさらに含むことを特徴とする請求項８に記載のフラッシュメモリにデータを書き込む方法。
【請求項１１】
前記データが上位ページから順次書き込まれる場合に、前記有効な論理ページを検索するのは、１つ以上の同じ論理ページ番号を有する論理ページのうち、最も下位のページを検索することにより行われることを特徴とする請求項１０に記載のフラッシュメモリにデータを書き込む方法。
【請求項１２】
前記データがインプレース優先方式で書き込まれる場合に、前記有効な論理ページを検索するのは、１つ以上の同じ論理ページ番号を有する論理ページのうち、インプレース位置にあるページを除いたページを選定し、前記選定されたページのうち、最も下位のページを検索することでさなれることを特徴とする請求項１０に記載のフラッシュメモリにデータを書き込む方法。
【請求項１３】
所定数のセクターからなるページを有するブロックを一つ以上有し、前記セクターまたは前記ページ単位でデータを書き込み、前記ブロック単位でデータを消去するフラッシュメモリにデータを書き込む方法において、
書き込みたいデータを格納できる空いているセクターが現在のブロックに存在するかどうかを判断する第１のステップと、
前記判断の結果、空いているセクターが存在すると、前記空いているセクターにデータを書き込み、前記空いているセクターが位置した物理ページと同じ物理ページに前記データに対する論理セクター番号を書き込む第２のステップと
を含むことを特徴とするフラッシュメモリにデータを書き込む方法。
【請求項１４】
前記論理セクター番号を書き込むのは、物理ページの主領域でデータを書き込んだセクターの位置と対応する補助領域での位置に書き込むことを特徴とする請求項１３に記載のフラッシュメモリにデータを書き込む方法。
【請求項１５】
前記空いているセクターは、前記書き込みたいデータとセクターオフセットが一致する空いているセクターであることを特徴とする請求項１３に記載のフラッシュメモリにデータを書き込む方法。
【請求項１６】
前記第１のステップは、前記書き込みたいデータとセクターオフセットが一致し、次のセクターが空いている空いたセクターが現在のブロックに存在するかを判断することを特徴とする請求項１５に記載のフラッシュメモリにデータを書き込む方法。
【請求項１７】
所定数のセクターからなるページを有するブロックを一つ以上有し、前記セクターまたは前記ページ単位でデータを書き込み、前記ブロック単位でデータを消去するフラッシュメモリにおいて、
書き込みたいデータの最も最近に書き込まれた論理ページ番号を有する物理ページに、前記書き込みたいデータとオフセットとが一致するセクターが空いているかどうかを判断し、前記判断の結果、前記オフセットが一致するセクターが空いていると、前記物理ページの前記オフセットが一致するセクターにデータを書き込み、
前記判断の結果、前記オフセットが一致するセクターが空いていないと、空いている物理ページを選択し、前記データとオフセットが一致するセクターにデータを書き込み、前記選択された空いている物理ページに前記データに対する論理ページ番号を書き込むことを特徴とするフラッシュメモリ。
【請求項１８】
前記空いたセクターが存在するかを判断することは、書き込みたいデータの最も最近に書き込まれた論理ページ番号を有する物理ページに前記書き込みたいデータとオフセットが一致するセクターが空いているか、及び前記物理ページに前記セクターの次のセクターが全て空いているかを共に判断することであることを特徴とする請求項１６に記載のフラッシュメモリ。
【請求項１９】
前記書き込んだ論理ページ番号を有する既存の有効な論理ページに書き込まれたデータのうち、前記書き込まれたデータ以外のデータを前記選択された空いている物理ページにコピーすることを特徴とする請求項１７または１８に記載のフラッシュメモリ。
【請求項２０】
所定数のセクターからなるページを有するブロックを一つ以上有し、前記セクターまたは前記ページ単位でデータを書き込み、前記ブロック単位でデータを消去するフラッシュメモリにおいて、
書き込みたいデータの最も最近に書き込まれた論理ページ番号を有する物理ページに前記書き込みたいデータを格納できる空いているセクターが存在するかどうかを判断し、前記判断の結果、空いているセクターが存在すると、前記物理ページの空いているセクターにデータを書き込み、前記物理ページに前記データに対する論理セクター番号を書き込み、
前記判断の結果、空いているセクターが存在しないと、空いている物理ページを選択し、空いているセクターにデータを書き込み、前記選択された空いている物理ページに前記データに対する論理ページ番号及び論理セクター番号を書き込むことを特徴とするフラッシュメモリ。
【請求項２１】
前記論理セクター番号を書き込むのは、物理ページの主領域でデータを書き込んだセクターの位置と対応する補助領域での位置に書き込むことを特徴とする請求項２０に記載のフラッシュメモリ。
【請求項２２】
前記書き込んだ論理ページ番号を有する既存の有効な論理ページに書き込まれたデータのうち、前記書き込んだデータ以外のデータ、及びそのデータの論理セクター番号を前記選択された空いている物理ページにコピーすることを特徴とする請求項２０に記載のフラッシュメモリ。
【請求項２３】
所定数のセクターからなるページを有するブロックを一つ以上有し、前記セクターまたは前記ページ単位でデータを書き込み、前記ブロック単位でデータを消去するフラッシュメモリにおいて、
書き込みたいデータを格納できる空いているセクターが現在のブロックに存在するかどうかを判断し、空いているセクターが存在すると、前記空いているセクターにデータを書き込み、前記空いているセクターが位置した物理ページと同じ物理ページに前記データに対する論理セクター番号を書き込むことを特徴とするフラッシュメモリ。
【請求項２４】
前記論理セクター番号を書き込むのは、物理ページの主領域でデータを書き込んだセクターの位置と対応する補助領域での位置に書き込むことを特徴とする請求項２３に記載のフラッシュメモリ。
【請求項２５】
前記空いているセクターは、前記書き込みたいデータとセクターオフセットが一致する空いているセクターであることを特徴とする請求項２３に記載のフラッシュメモリ。
【請求項２６】
前記空いているセクターが現在のブロックに存在するかを判断することは、前記書き込みたいデータとセクターオフセットが一致し、次のセクターが空いている空いたセクターが現在のブロックに存在するかを判断することであることを特徴とする請求項２５に記載のフラッシュメモリ。
【請求項２７】
複数のブロックからなるフラッシュメモリにおいて、
前記ブロックのうちの一部のブロックを、論理・物理マッピング情報を格納するために、別のマップブロックに割り当て、前記マップブロックは、前記マッピング情報をセグメントに分割して格納している一つ以上のマップセグメントユニットを含み、前記マッピング情報の変更がある場合には、前記変更された情報を格納しているマップセグメントユニットを前記マップブロックの空いているユニットに書き込むことにより、前記マッピング情報を更新することを特徴とするフラッシュメモリ。
【請求項２８】
１つのマップブロック内に同じシリアル番号を有するマップセグメントユニットが複数ある場合には、最も最近に書き込まれたマップセグメントユニットのみが有効であることで認められることを特徴とする請求項２７に記載のフラッシュメモリ。
【請求項２９】
前記論理・物理マッピング情報は、論理ブロック番号と物理ブロック番号との間のマッピング情報であることを特徴とする請求項２７に記載のフラッシュメモリ。
【請求項３０】
前記論理・物理マッピング情報は、論理ページ番号と物理ページ番号との間のマッピング情報であることを特徴とする請求項２７に記載のフラッシュメモリ。
【請求項３１】
前記論理・物理マッピング情報は、論理セクター番号と物理セクター番号との間のマッピング情報であることを特徴とする請求項２７に記載のフラッシュメモリ。
【請求項３２】
前記格納する論理・物理マッピング情報の量が１つのマップブロックを超えないことを特徴とする請求項２７に記載のフラッシュメモリ。
【請求項３３】
前記マップセグメントユニットは、前記論理・物理マッピング情報をセグメントに分割して格納しているマップセグメントと、
前記論理・物理マッピング情報を安全に保護するための付加情報を書き込む補助領域とを含むことを特徴とする請求項２７に記載のフラッシュメモリ。
【請求項３４】
前記付加情報は、前記分割して格納されたマップセグメントに係るシリアル番号を表示するセグメント番号フィールドと、
有効なマッピング情報に係るマップセグメントユニットを既存のマップブロックから新しいマップブロックにコピーするときに番号を増加して書き込むエイジフィールドとを含むことを特徴とする請求項３３に記載のフラッシュメモリ。
【請求項３５】
前記付加情報は、マップセグメントを完全に書き込んでから書き込むことで、前記マップセグメントを書き込む途中でエラーが発生していないことを確認する有効マークフィールドを含むことを特徴とする請求項３３に記載のフラッシュメモリ。
【請求項３６】
前記付加情報は、１つ以上のビットを０として有するビット列からなり、前記１つ以上のビットが１に変更されたことがあるかによって、前記マップブロックを消去する途中でエラーがあったかどうかを知らせるシグネチャフィールドをさらに含むことを特徴とする請求項３３に記載のフラッシュメモリ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、フラッシュメモリ(flash memory)をアクセス(access)する方法に関し、より詳しくは、論理・物理マッピング(logical-physical mapping)手法を用いてフラッシュメモリのアクセス時に性能低下を最小限に抑える方法、及びフラッシュメモリに前記論理・物理マッピングに関する情報を効率的に格納し管理する方法、及びこれらの方法を用いたフラッシュメモリに関する。
【背景技術】
【０００２】
フラッシュメモリは、ハードディスクのように、不揮発性でありながらも速いアクセス速度を有し、電力を少なく消耗するため、組み込み型システム(embedded system)またはモバイルデバイス(mobile device)などの応用に多く使用されている。
ところで、このようなフラッシュメモリは、そのハードウェアの特性を考慮するとき、既に書き込まれたメモリセクターに書き込み(write)演算を行うためには、そのセクターが含まれたブロックの全体を消去する(erase)演算を先に行わなければならず、これがフラッシュメモリの性能を低下させる主な要因となっていた。
【０００３】
このような書き込みの前の消去(erase before write)を行う問題を解決するために、論理アドレス(logical address)や物理アドレス(physical address)の概念が導入された。即ち、ホスト段から要求される論理アドレスに対する読み出し・書き込み演算は、種々のマッピングアルゴリズムによって実際のフラッシュメモリの物理アドレスに対する読み出し・書き込み演算に変更される。このとき、物理的なフラッシュメモリの状態を考慮しているため、性能を最大にすることができる。
【０００４】
最近、フラッシュメモリシステムの性能を向上させるために、連続されるフラッシュ演算をバッファリングして置き、一度に処理できるフラッシュメモリが開発されているが、このようなフラッシュメモリを大ブロック(large block)フラッシュメモリという。しかし、既存の論理・物理マッピングアルゴリズムを大ブロックフラッシュメモリにそのまま適用すると、大ブロックフラッシュメモリの利点を十分に生かすことができなかった。従って、本発明のように、大ブロックフラッシュメモリのための効率的な論理・物理マッピングアルゴリズムが要求されていた。
【０００５】
従来のフラッシュメモリ論理・物理マッピング手法に関する技術は、「M-Systems Flash Disk Pioneer」社により出願された特許文献１や特許文献２、「Mitsubishi」社により出願された特許文献３、及び「三星電子」により出願された特許文献４などに記載されている。このような従来の技術において、フラッシュメモリのアクセス方法の核心は、ホスト段から要求される論理セクターへの書き込み要求に応じて、フラッシュメモリの実際の物理セクターにどのように書き込みを効率的に行えるかにある。ここで、フラッシュメモリの消去単位をブロックとし、読み出し・書き込み単位をセクターとすると、従来の技術は、大別してセクターマッピング手法とブロックマッピング手法とに分けられる。
【０００６】
図１は、従来のセクターマッピングの一例を示す図である。セクター番号とそのオフセットとからなる仮想アドレス(virtual address)は、フラッシュメモリに格納されているセクター単位のマッピング情報により論理アドレス(logical address)に変換される。次に、求められた論理アドレスの上位ビットから論理ブロック番号を求められるが、メインメモリ(main memory)に格納されている論理ブロック-物理ブロックテーブルから最終の物理アドレスを求めることになる。
【０００７】
図２は、従来のブロックマッピングの一例を示す図である。仮想ブロック(virtual block)は、それとマッピングされるメインブロック(primary block)と補助ブロック(replacement block)とを有する。即ち、ブロック単位のマッピング情報により、ある論理ブロックの１つのセクターは、他のブロックの１つのセクターにマッピングされることになる。このとき、メインブロックの該当セクターに他のデータが既に書き込まれている場合には、補助ブロックにデータが書き込まれることになる。
【０００８】
フラッシュメモリの主要演算には、読み出し(read)、書き込み(write)、消去(erase)の三つの演算がある。本発明は、主として読み出し・書き込み演算に関連しており、この読み出し・書き込み演算は、その動作の面でそれほど大差がないことから、ここでは、従来技術の書き込み演算の動作を示す図である。
ホストは、データをフラッシュメモリに書き込むために、論理セクター番号(Logical Sector Number；以下、ＬＳＮとも称する)を伝達する。図１に示すようなセクターマッピング手法において、ＬＳＮやＰＳＮ(Physical Sector Number；以下、ＰＳＮとも称する)に対するマッピングテーブル(mapping table)が存在しているため、該当のＰＳＮにデータを書き込めば良い。このとき、該当のＰＳＮに既にデータが存在する場合には空いている他のＰＳＮを検索してデータを書き込み、マッピング情報を変更する。
【０００９】
図２に示すようなブロックマッピング手法においては、与えられたＬＳＮから先ずＬＢＮ(Logical Block Number；以下、ＬＢＮと称する)を求め、存在しているＬＢＮ-ＰＢＮマッピングテーブルからＰＢＮを検索し、オフセットが一致するＰＳＮを検索してデータを書き込んでいる。セクターマッピングの場合と同様に、既にデータが書き込まれている場合には、書き込み可能なブロックのセクターにデータを書き込み、マッピング情報を変更する。
【００１０】
最近開発された大ブロックフラッシュメモリは、二つ以上のセクターへの読み出し・書き込み手法を提供している。即ち、フラッシュメモリの演算単位をページとし、その大きさが４つのセクターと同じであると、４つのセクターを一度に読み出すか、書き込むことができる。しかし、既存の論理・物理マッピングアルゴリズム(logical-physical mapping algorithm)は、ホストのセクターの大きさとフラッシュメモリの演算単位とが同じであると見なしているから、既存のアルゴリズムを大ブロックフラッシュメモリに適用すれば、大ブロックフラッシュメモリの利点を生かすことができない。特に、大ブロックフラッシュメモリは、一つ以上の連続したセクターへの書き込み演算(multiple sector write)において良好な性能を発揮できるにも関らず、既存のアルゴリズムでは、このような特性を考慮していなかった。
【００１１】
【特許文献１】米国特許第５，４０４，４８５号
【特許文献２】米国特許第５，９３７，４２５号
【特許文献３】米国特許第５，９０５，９９３号
【特許文献４】米国特許第６，３８１，１７６号
【発明の開示】
【発明が解決しようとする課題】
【００１２】
本発明は、上記問題点に鑑みなされたものであり、大ブロックフラッシュメモリに適した論理・物理マッピングアルゴリズムを提供することを目的とする。
また、本発明は、論理・物理マッピング情報管理方法を用いてフラッシュメモリのシステムの性能を最大化し、電源の突然の異常時にもシステムを安全に復旧できるようにする方法を提供することを目的とする。
【課題を解決するための手段】
【００１３】
上記の目的を達成するため、本発明による方法においては、所定数のセクターからなるページを有するブロックを一つ以上有し、前記セクターまたは前記ページ単位でデータを書き込み、前記ブロック単位でデータを消去するフラッシュメモリにデータを書き込む方法において、書き込みたいデータの最も最近に書き込まれた論理ページ番号を有する物理ページに、前記書き込みたいデータとオフセットが一致するセクターが空いているかどうかを判断する第１のステップと、前記判断の結果、前記オフセットが一致するセクターが空いていると、前記物理ページの前記オフセットが一致するセクターにデータを書き込む第２のステップと、前記判断の結果、前記オフセットが一致するセクターが空いていないと、空いている物理ページを選択し、前記データとオフセットが一致するセクターにデータを書き込み、前記選択された空いている物理ページに前記データに対する論理ページ番号を書き込む第３のステップとを含むことを特徴とする。
【００１４】
本発明による方法においては、書き込みたいデータの最も最近に書き込まれた論理ページ番号を有する物理ページに前記書き込みたいデータを格納できる空いているセクターが存在するかどうかを判断する第１のステップと、前記判断の結果、空いているセクターが存在すると、前記物理ページの空いているセクターにデータを書き込み、前記物理ページに前記データに対する論理セクター番号を書き込む第２のステップと、前記判断の結果、空いているセクターが存在しないと、空いている物理ページを選択し、空いているセクターにデータを書き込み、前記選択された空いている物理ページに前記データに対する論理ページ番号及び論理セクター番号を書き込む第３のステップとを含むことを特徴とする。
【００１５】
本発明による方法においては、書き込みたいデータを格納できる空いているセクターが現在のブロックに存在するかどうかを判断する第１のステップと、前記判断の結果、空いているセクターが存在すると、前記空いているセクターにデータを書き込み、前記空いているセクターが位置した物理ページと同じ物理ページに前記データに対する論理セクター番号を書き込む第２のステップとを含むことを特徴とする。
【００１６】
本発明による方法においては、所定数のセクターからなるページを有するブロックを一つ以上有し、前記セクターまたは前記ページ単位でデータを書き込み、前記ブロック単位でデータを消去するフラッシュメモリにおいて、書き込みたいデータの最も最近に書き込まれた論理ページ番号を有する物理ページに前記書き込みたいデータとオフセットとが一致するセクターが空いているかどうかを判断し、前記判断の結果、前記オフセットが一致するセクターが空いていると、前記物理ページの前記オフセットが一致するセクターにデータを書き込み、前記判断の結果、前記オフセットが一致するセクターが空いていないと、空いている物理ページを選択し、前記データとオフセットが一致するセクターにデータを書き込み、前記選択された空いている物理ページに前記データに対する論理ページ番号を書き込むことを特徴とする。
【００１７】
本発明による方法においては、フラッシュメモリは、書き込みたいデータの最も最近に書き込まれた論理ページ番号を有する物理ページに前記書き込みたいデータを格納できる空いているセクターが存在するかどうかを判断し、前記判断の結果、空いているセクターが存在すると、前記物理ページの空いているセクターにデータを書き込み、前記物理ページに前記データに対する論理セクター番号を書き込み、前記判断の結果、空いているセクターが存在しないと、空いている物理ページを選択し、空いているセクターにデータを書き込み、前記選択された空いている物理ページに前記データに対する論理ページ番号及び論理セクター番号を書き込むことを特徴とする。
【００１８】
本発明による方法においては、フラッシュメモリは、書き込みたいデータを格納できる空いているセクターが現在のブロックに存在するかどうかを判断し、空いているセクターが存在すると、前記空いているセクターにデータを書き込み、前記空いているセクターが位置した物理ページと同じ物理ページに前記データに対する論理セクター番号を書き込むことを特徴とする。
【００１９】
本発明による方法においては、複数のブロックからなるフラッシュメモリにおいて、前記ブロックのうちの一部のブロックを、論理・物理マッピング情報を格納するために、別のマップブロックに割り当て、前記マップブロックは、前記マッピング情報をセグメントに分割して格納している一つ以上のマップセグメントユニットを含み、前記マッピング情報の変更がある場合には、前記変更された情報を格納しているマップセグメントユニットを前記マップブロックの空いているユニットに書き込むことにより、前記マッピング情報を更新することを特徴とする。
【発明の効果】
【００２０】
このような本発明に係るフラッシュメモリのアドレスマッピング方法、マッピング情報管理方法及びそれらの方法を用いたフラッシュメモリによれば、大ブロックフラッシュメモリの特性を反映した論理・物理アドレスマッピング方法及び論理・物理アドレスマッピング情報管理方法を提案することにより、大ブロックフラッシュメモリの性能を向上させ、突然の電源の切断時にもシステムを安全に復旧できるという効果がある。
【発明を実施するための最良の形態】
【００２１】
以下、本発明の好ましい実施の形態を、添付図面に基づいて詳しく説明する。
本発明による利点及び特徴、かつ、それらを達成する方法は、添付図面に基づいて詳しく後述される実施形態によって明らかになるだろう。
【００２２】
図３は、フラッシュメモリが動作するシステムの全体構造を示す図である。ＸＩＰ可能メモリ(XIP-able memory)３１１は、ＲＯＭ(Read-Only Memory)またはＲＡＭ(Random-Access Memory)のように、ＸＩＰ(Execute-In-Place)が可能なメモリである。これは、即ち、プログラムコードが搭載されて実行可能なメモリを意味するが、このうち、ＲＡＭは揮発性であり、ＲＯＭは不揮発性である。フラッシュメモリ３１２は、前記のようなＸＩＰ可能メモリ３１１ではなく、単にデータを格納するメモリであって、不揮発性である。ＣＰＵ３１３は、直接実行可能なメモリに搭載されたフラッシュメモリアクセスコードを実行することにより、外部ホスト(external host)３００から伝達されてきた読み出し・書き込み演算要求をフラッシュメモリの読み出し・書き込み演算に変更する役割を担う。
【００２３】
図４及び図５は、実際の１２８ＭＢ ＮＡＮＤ型のフラッシュメモリの構成を示す図である。本発明は、その他に、異なる大きさの格納容量を有するフラッシュメモリにも適用できるのは言うまでも無い。図４に示すような小ブロック(small block)フラッシュメモリは、外部ホストから要求されるデータの読み出し・書き込み演算の単位と実際にフラッシュメモリが提供するフラッシュメモリの読み出し・書き込み演算の単位とが同じであるシステムである。例えば、外部ホストから５１２Ｂ単位で読み出しまたは書き込みが要求されると、フラッシュメモリでも同様に、５１２Ｂ単位で読み出したり書き込みたりする作業を行う。図４に示すように、１２８ＭＢフラッシュメモリの場合に、１つのページは、主領域５１２Ｂと補助領域１６Ｂとからなり、消去単位であるブロックは、３２個のページからなっている。
【００２４】
図５に示すような大ブロック(large block)フラッシュメモリの場合は、フラッシュメモリの読み出し・書き込みの単位が外部ホストから要求される読み出し・書き込み単位の倍数となる。特に、図５の例においては、フラッシュメモリの１つのページの大きさは、４つのセクターの大きさと同じであり、消去単位であるブロックは、６４ページからなっていることが分かる。
【００２５】
図６は、大ブロックフラッシュメモリの読み出し・書き込み単位であるページの基本フォーマットを示す図である。最近通用している大ブロックフラッシュメモリは、ページの大きさが小ブロックフラッシュメモリにおけるページの四倍であるので、主領域(main area)には４つのセクターが格納できる。しかし、４つ以上またはその以下のセクターが１つのページに格納されても本発明による概念が同様に適用されるのは当業界の通常の知識を有する者にとっては、容易に想到できることであるだろう。補助領域(spare area)には種々のメタ情報が格納できるが、主なメタ情報としては、各セクターごとの論理セクター番号である「ＬＳＮ(logical sector number)」とフラッシュメモリの１つのページに対する論理ページ番号である「ＬＰＮ(logical sector number)」とが格納できる。このように、論理・物理マッピング情報がフラッシュメモリの各ページに格納されても良いが、これとは異なり、フラッシュメモリの全体領域のうちの一部の領域にマッピングテーブル情報を別々に格納する方法も考えられる。
【００２６】
本発明は、ホスト段から要求される論理アドレスに対する読み出し・書き込み要求を大ブロックフラッシュメモリの物理アドレスに対する読み出し・書き込み要求に切り替える方法に関するものであり、大ブロックの論理・物理アドレスマッピング方法と、論理・物理アドレスマッピング情報管理方法とに分けて説明する。
【００２７】
［論理・物理アドレスマッピング方法］
先ず、大ブロックの論理・物理アドレスマッピングアルゴリズムについて説明する。フラッシュメモリの主要演算としては、書き込み演算と読み出し演算があるが、読み出し演算は、書き込み演算の逆にしたものに過ぎず、ここでは、書き込み演算についてのみ説明する。
【００２８】
外部ホストから要求される書き込み演算には、二つの種類がある。その一つは、ＬＳＮ及び該当のデータを入力する単一セクター書き込み(single sector write)演算であり、もう一つは、開始ＬＳＮ、連続したＬＳＮの個数及び該当のデータを入力する多重セクター書き込み(multiple sector write)演算である。大ブロックフラッシュメモリシステムは、一つ以上のセクターへの同時書き込み演算が可能であり、多重セクター書き込み演算の際において良好な性能を発揮することができる。ところで、最近通用されている大容量のフラッシュメモリは、１つのページが４つのセクターからなっており、本発明の一例として、１つのページが４つのセクターからなる大ブロックフラッシュメモリの論理・物理アドレスマッピングアルゴリズムに関して述べる。
【００２９】
大ブロックフラッシュメモリは、小ブロックとは異なり、１つのページが複数のセクターからなり、多重セクター書き込みが可能な構造であるという点で、小ブロックに比べて様々な論理・物理アドレスマッピングアルゴリズムが適用できる。即ち、従来の小ブロックフラッシュメモリシステムでは、ブロック及びセクターが論理マッピングの基本単位であるに対し、大ブロックフラッシュメモリでは、ブロック、セクターの他に、ページという基本マッピング単位が存在する。前述したように、単一セクター書き込みの場合、大ブロックフラッシュメモリの書き込み演算の入力は、ＬＳＮ及び該当のデータとなるが、マッピングアルゴリズムによってフラッシュメモリの物理アドレスであるＰＳＮ(Physical Sector Number)に変換される。
【００３０】
先ず、ＬＳＮに対応する論理ブロック番号であるＬＢＮ(Logical Block Number)は、フラッシュメモリのブロック当たりのセクター数によって計算される。計算されたＬＢＮに対応する物理ブロック番号であるＰＢＮ(Physical Block Number)は、ＬＢＮとＰＢＮとの間のマッピングテーブル(mapping table)を参照して決定される。ＰＢＮを決定するさらに他の方法には、フラッシュメモリの各ブロック毎の一定の領域にＬＢＮを書き込みことにより、論理・物理ブロックマッピング情報を格納し、ＬＢＮに対応するＰＢＮを検索する方法もある。
【００３１】
前記検索されたＰＢＮからセクターアドレスを求める方法は、大別して２つあるが、その１つは、論理ブロックと物理ブロックとの間のセクターオフセットが一致するものとし、セクターアドレスを求める方法と、もう１つは、新たにマッピング情報を格納し、セクターオフセットの一致を必要としない方法である。前者の方法は、従来の技術において既に提示されており、本発明では、後者の方法を大ブロックフラッシュメモリに適用しているが、細部的には、全て６つの方法に分けられる。一番目や二番目の方法は、ページマッピング、三番目や四番目の方法は、ページマッピングを応用したセクターマッピング、五番目や六番目の方法は、ページマッピングの無いセクターマッピング方法である。ページマッピングのためには、図６に示すようにＬＰＮを書き込む必要があり、セクターマッピングのためには、図６に示すようにＬＳＮを書き込む必要がある。
【００３２】
一番目の方法は、１対１ページマッピング方法で、１つの論理アドレスに対応する物理アドレスをただ１つのみ存在させる方法である。図７は、本発明による１対１ページマッピング過程を示すフローチャートである。先ず、外部ホスト３００から作業を行いたい１つ以上のセクターのＬＳＮを入力される（Ｓ１１０）。次に、前記ＬＳＮからＬＰＮ及びＬＢＮを計算し、予め定義されているブロック単位のマッピング情報を用いてＰＢＮを決定する（Ｓ１２０）。前記決定されたＰＢＮに該当する物理ブロックに対し以下の過程を行う。先ず、前記物理ブロックに該当ＬＰＮが使用されたことがあるかを判断する（Ｓ１３０）。大ブロックフラッシュメモリに適用するために、本発明によるページの概念を利用して、特定のページには特定の各セクターが含まれることで予め定義されている。従って、前記該当ＬＰＮとは、前記定義により前記ＬＳＮが含まれるページのＬＰＮを意味する。
【００３３】
１対１ページマッピング手法では、１つのＬＰＮに対し、１つのＰＰＮ(physical page number)が決定されるため、決定されたＰＰＮに入力データを書き込みできるかどうかを検査する必要がある。前記ステップＳ１３０での判断の結果、ＬＰＮが使用されたことがないと、インプレース(In-place)位置のページが空いているかどうかを判断し(Ｓ１３１)、ページが空いていると、インプレース位置にデータを書き込み(Ｓ１３２)、その位置に該当するページの補助領域にＬＰＮを書き込み(Ｓ１３３)、終了する。前記インプレース位置とは、既存の物理・論理マッピング情報によって予め指定されたデフォルト(default)の位置をいう。即ち、既に定義されたマッピング情報によって特定のＬＰＮを有するページのオフセットには特定のＬＳＮを有するセクターが書き込まれるように予め設定された位置を意味している。
【００３４】
このように、データは、自分のインプレース位置に書き込むことを基本とするが、他のデータが既に書き込まれており、インプレース位置に書き込めない場合には、空いている物理ページのうち、上位のページから順次書き込めば良い。
前記ステップＳ１３０での判断の結果、ＬＰＮが使用されたことがあると、有効なＬＰＮを有するページ、即ち、前記使用されたＬＰＮを有するページが複数あれば、最も最近に生成されたページにオフセットが一致するセクター及び次のセクターが空いているどうかを判断し(Ｓ１４０)、空いていると、オフセットが一致するセクターの位置にデータを書き込み(Ｓ１５０)、終了する。ここで、オフセットとは、１つのページにてセクターが占めるように決まっている位置を意味するもので、例えば、あるページにD4、D5、D6及びD7が順に書き込まれることで予め定義されていれば、D4、D5、D6及びD7は、それぞれ0、1、2及び3をオフセット値として有することになる。
【００３５】
本発明においては、多重セクター書き込みにおいて高い性能を得るために、該当のセクターが空いていても、当該のページの次のセクターが全て空いていないと、前記該当のセクターにデータを書き込まないようにしている。これは、殆どの場合、連続したセクターへの書き込み要求が多く、次のセクターが空いていない状態で該当のセクターへの書き込み演算を行った後、その次の要求が連続したセクターに要求されると、費用が高い更新演算を行わなければならないためである。しかし、多重セクター演算の場合、予め何個のセクターを使用するかを明らかにする応用(application)もあり得るが、この場合には、必ずしも次のセクターが全て空いている必要はなく、前記ステップＳ１４０でオフセットが一致するセクターが存在するかを判断するだけでも良い。
【００３６】
前記ステップＳ１３１での判断の結果、インプレース位置のページが空いていないと、現在のブロックにて空いているページが存在するかどうかを判断し(Ｓ１４１)、空いているページが存在しないと、次の新しいブロックを割り当てた後(Ｓ１４２)、新しいブロックのインプレース位置にデータを書き込み(Ｓ１３２)、その位置に該当するページの補助領域にＬＰＮを書き込み(Ｓ１３３)、終了する。
【００３７】
前記ステップＳ１４１での判断の結果、空いているページが存在すると、空いているページのうちの１つのページを選択し、前記ＬＳＮとオフセットが一致するセクターの位置にデータを書き込み(Ｓ１５１)、前記選択されたページの補助領域にＬＰＮを書き込む(Ｓ１６０)。前記空いているページのうちの１つを選択するのは、様々な方法を用いて行うことができる。即ち、上位ページから順次空いているページを選択することができ、その逆に選択することも可能である。最後に、１対１ページマッピングを維持するために、既存の有効なＬＰＮに該当するデータをコピーしてきた後(Ｓ１７０)、終了する。
【００３８】
図８は、本発明による１対１ページマッピング方法の実例を示す図である。大ブロックフラッシュメモリは、多重セクター書き込みが可能であるため、４つのデータを同時に書き込めるものとする。先ず、４つのデータＤ０、Ｄ１、Ｄ２及びＤ３を現在のブロックの一番目のページ(ＰＰＮ=０)に順に書き込み(Ｓ１３２)、補助領域にＬＰＮ値として０を書き込む(Ｓ１３３)。次いで、次の４つのデータＤ４、Ｄ５、Ｄ６及びＤ７を二番目のページ(ＰＰＮ=1)に順に書き込み(Ｓ１３２)、補助領域にＬＰＮ値として1を書き込む(Ｓ１３３)。次に、Ｄ０及びＤ１を書き込む場合には、該当のＬＰＮ(「０」)が書き込まれたことがあるから(Ｓ１３０の例)、有効なＬＰＮを有する一番目のページ(ＰＰＮ=０)に該当のオフセットを有するセクターが空いているかどうかを判断する(Ｓ１４０)。セクターが空いていないから、次の空いているページ(ＰＰＮ=２)の一番目のセクターにＤ０を、二番目のセクターにＤ１を書き込み(Ｓ１５１)、補助領域に該当のＬＰＮ(「０」)を書き込む(Ｓ１６０)。かつ、既存の有効なＬＰＮに該当する残りのデータ(ＰＰＮ=０に書き込まれた残りのデータ)、即ち、Ｄ２及びＤ３をオフセットに合わせて現在のページ(ＰＰＮ=２)にコピーする(Ｓ１７０)。
【００３９】
次に、Ｄ３を書き込む場合には、次の空いているページ(ＰＰＮ=３)のオフセットが一致するセクター位置、即ち、四番目のセクターにＤ３を書き込み(Ｓ１５１)、該当のＬＰＮ(「０」)を書き込んだ後(Ｓ１６０)、三番目のページ(ＰＰＮ=２)から残りのデータ、即ち、Ｄ０、Ｄ１及びＤ２をオフセットに合わせて現在のページ(ＰＰＮ=３)にコピーする。
二番目の方法は、１対ｎページマッピング方法であり、図９にそのフローチャートを示す図である。一番目の方法とは異なり、このマッピング方法は、１つのブロック内に有効なページが１つ以上存在できるようにする方法である。即ち、該当のＬＳＮのセクターオフセットは維持したまま、物理アドレスに書き込みを行うが、既存の有効なページから残りの各セクターをコピーしてくるステップは存在しない。これは、本方法では、１つ以上のページに有効なデータが存在できることから、既存の有効なＬＰＮに対するデータをコピーするステップが必要なくなるためである。従って、前記図７のフローチャートと比較すると、残りの各ステップは全て同様であるが、図７のステップＳ１７０のようなステップが存在しないという点で異なる。
【００４０】
図１０は、本発明による１対ｎページマッピング方法の実例を示す図である。先ず、４つのデータＤ０、Ｄ１、Ｄ及びＤ３を現在のブロックの一番目のページ(ＰＰＮ=０)に順に書き込み(Ｓ２３２)、補助領域にＬＰＮ値として０を書き込む(Ｓ２３３)。かつ、次の４つのデータＤ４、Ｄ５、Ｄ６及びＤ７を二番目のページ(ＰＰＮ=１)に順に書き込み(Ｓ２３２)、補助領域にＬＰＮ値として１を書き込む(Ｓ２３３)。次に、Ｄ０及びＤ１を書き込む場合には、該当のＬＰＮ(「０」)が書き込まれたことがあるから(ステップＳ２３０の例)、最も最近に書き込まれたＬＰＮを有する一番目のページ(ＰＰＮ=０)に該当のオフセットを有するセクターが空いているかどうかを判断する(Ｓ２４０)。セクターが空いていないから、次の空いているページ(ＰＰＮ=２)の一番目セクターにＤ０を、二番目のセクターにＤ１を書き込み(Ｓ２５１)、補助領域に該当のＬＰＮ(「０」)を書き込む(Ｓ２６０)。
【００４１】
次に、Ｄ３を書き込む場合には、ステップＳ２４０での判断結果、現在のページ(ＰＰＮ=２)に該当のオフセットが一致する四番目のセクターが空いているため、前記四番目のセクターにＤ３を書き込む(Ｓ２５０)。その次に、Ｄ１を書き込む場合には、最も最近に書き込まれたＬＰＮを有するページ(ＰＰＮ=２)にオフセットが一致するセクターが空いていないため(Ｓ２４０のいいえ)、次の空いているページ(ＰＰＮ=３)のオフセットが一致する二番目のセクターにＤ１を書き込み(Ｓ２５１)、そのページの補助領域にＬＰＮを書き込んだ後(Ｓ２６０)、終了する。
【００４２】
三番目の方法は、本発明による１対１ページマッピングを応用したセクターマッピング方法である。一番目の方法で提示された１対１ページマッピング方法とほぼ同じであるが、書き込みを行うときにセクターオフセットを維持せず、ページ内で自由に書き込む方法である。即ち、セクターオフセットは維持せずに書き込むが、有効なページは１つのブロックに１つとだけ存在するようにするために、該当のページに書き込みが終わった後、既存の有効なページから残りの各セクターをコピーしてくる方式である。図１１は、１対１ページマッピングを応用したセクターマッピング方法を示すフローチャートである。図７の１対１ページマッピングとは異なり、セクターオフセットを維持しないため、セクター単位のマッピング情報を示すＬＳＮを格納する必要がある。このとき、ＬＳＮ、ＬＰＮは、該当のデータと同時に書き込むことが可能である。
【００４３】
先ず、外部ホスト３００から作業を行いたい１つ以上のセクターのＬＳＮを入力される(Ｓ３１０)。次いで、前記ＬＳＮからＬＰＮ及びＬＢＮを計算し、予め定義されているブロック単位のマッピング情報を用いてＰＢＮを決定する(Ｓ３２０)。前記決定されたＰＢＮに該当する物理ブロックに対し以下の過程を行う。先ず、前記物理ブロックに該当のＬＰＮが使用されたことがあるかどうかを判断する(Ｓ３３０)。前記ステップＳ３３０での判断の結果、ＬＰＮが使用されたことがないと、インプレース(In-place)位置のページが空いているかを判断し(Ｓ３３１)、ページが空いていると、インプレース位置にデータを書き込み(Ｓ３３２)、その位置に該当する前記ページの補助領域にＬＳＮを書き込み、前記補助領域の所定の位置にＬＰＮを書き込み(Ｓ３３３)、終了する。前記その位置に該当する補助領域にＬＳＮを書き込むというのは、物理ページの主領域でデータを書き込んだセクターの位置と対応する補助領域での位置に書き込むことを意味する。例えば、一番目のセクターにデータを書き込んだ場合は、そのデータのＬＳＮは前記補助領域にてＬＳＮを書き込むように割り当てられた４つの桁うち、一番目の桁に書き込むことを意味する。
【００４４】
前記ステップＳ３３０での判断の結果、ＬＰＮが書き込まれたことがあると、前記書き込まれたＬＰＮのうち最も最近のものを有するページに空いているセクターが存在するかどうかを判断し(Ｓ３４０)、空いているセクターが存在すると、その空いているセクターにデータを書き込み(Ｓ３５０)、その位置に該当する前記ページの補助領域に前記データのＬＳＮを書き込む(Ｓ３８０)。
【００４５】
前記ステップＳ３３１での判断の結果、インプレース位置のページが空いていないと、現在のブロックに空いているページが存在するかを判断し(Ｓ３４１)、空いているページが存在しないと、次の新しいブロックを割り当てた後(Ｓ３４２)、新しいブロックのインプレース位置にデータを書き込み(Ｓ３３２)、その位置に該当するページの補助領域にＬＰＮ及びＬＳＮを書き込み(Ｓ３３３)、終了する。
【００４６】
前記ステップＳ３４１での判断の結果、空いているページが存在すると、空いているページのうち１つのページを選択し、そのページの任意の空いているセクター(通常、一番目のセクター)にデータを書き込み(Ｓ３５１)、前記選択されたページの補助領域にＬＰＮ及びＬＳＮを書き込む(Ｓ３６０)。最終に、１対１ページマッピングを維持するために、既存の有効なＬＳＮを有するデータ及びそのデータのＬＳＮをコピーした後(Ｓ３７０)、終了する。前記有効なＬＳＮとは、同一のＬＳＮが存在するとき、最も最近に書き込まれたＬＳＮを意味する。これを検索する方法は、同一のＬＰＮが複数存在するとき、最も最近に書き込まれたＬＰＮ(有効なＬＰＮ)を有するページを検索することになるが、そのページにも同一のＬＳＮが複数存在することもあるため、該当のＬＳＮのうち、最も最近のＬＳＮ(順次データを書き込んだ場合は、一番下位に書き込まれたＬＳＮ)を検索すれば良い。
【００４７】
図１２は、本発明による１対１ページマッピングを応用したセクターマッピング方法の実例を示す図である。先ず、二つのデータＤ０、Ｄ１を現在のブロックの一番目のページ(ＰＰＮ=０)に順に書き込み(Ｓ３３２)、そのページの補助領域のＬＳＮを書き込む四桁のうち一番目と二番目の桁に０、１をそれぞれ書き込み、ＬＰＮを書き込む部分に０を書き込む(Ｓ３３３)。次いで、次の４つのデータＤ４、Ｄ５、Ｄ６及びＤ７を二番目のページ(ＰＰＮ=１)に順に書き込み(Ｓ３３２)、補助領域にＬＳＮ値として４、５、６及び７をそれぞれ書き込み、ＬＰＮ値として１を書き込む(Ｓ３３３)。
【００４８】
次に、Ｄ０及びＤ１を書き込む場合には、該当のＬＰＮ(「０」)が書き込まれたことがあり(Ｓ３３０の例)、前記ＬＰＮを有するページ(ＰＰＮ=０)に空いているセクターが存在するかを判断する(Ｓ３４０)。ところで、空いているセクターが２つ存在するから、その空いているセクターにそれぞれＤ０、Ｄ１を書き込み(Ｓ３５０)、前記書き込んだＤ０、Ｄ１の位置に合わせて、補助領域のＬＳＮを書き込む部分のうち、三番目及び四番目の桁に０、１をそれぞれ書き込む(Ｓ３８０)。
【００４９】
次に、Ｄ３を書き込む場合には、次の空いているページ(ＰＰＮ=２)の空いているセクター、即ち、一番目のセクターにＤ３を書き込み(Ｓ３５１)、該当のＬＳＮ(「３」)及び該当のＬＰＮ(「０」)を書き込んだ後(Ｓ３６０)、一番目のページ(ＰＰＮ=０)から有効なＤ０、Ｄ１(最も最近に書き込まれたＤ０及びＤ１意味する)を現在のページ(ＰＰＮ=２)の空いているセクターにコピーする。次いで、Ｄ０、Ｄ１のＬＳＮである０、１を該当の位置、即ち、補助領域のＬＳＮを書き込む部分の二番目、三番目の桁にコピーする(Ｓ３７０)。次に、Ｄ１を書き込む場合には、現在のページ(ＰＰＮ=２)に空いているセクターが存在するため(Ｓ３４０の例)、そのセクターにＤ１を書き込み(Ｓ３５０)、該当のＬＳＮを書き込む位置に１を書き込む(Ｓ３８０)。
【００５０】
四番目の方法は、本発明による１対ｎページマッピングを応用したセクターマッピング方法である。二番目の方法とほぼ同じであるが、これもやはり、書き込みを行うとき、セクターオフセットを維持せず、ページ内で自由に書き込む点で異なっている。しかし、１つのブロック内に有効なセクターを有するページが１つ以上存在できるという点でほぼ同じである。ページ内で書き込むときには、一旦、セクターオフセットが一致する位置に書き込み、その桁に既にデータが書き込まれている場合には、左側から空いているセクターを見付けて書き込んで良く、右側から空いているセクターを見付けて書き込んでも良い。図１３は、１対ｎページマッピングを応用したセクターマッピング方法を示すフローチャートである。前記図１１のフローチャートと比較すると、残りのステップは、いずれも同じであるが、図１１のステップＳ３７０のようなステップが存在しないという点のみで異なっている。
【００５１】
図１４は、本発明による１対ｎページマッピング方法の実例を示す図である。先ず、二つのデータＤ０、Ｄ１を現在のブロックの一番目のページ(ＰＰＮ=０)に順に書き込み(Ｓ４３２)、そのページの補助領域のＬＳＮを書き込む四つの桁のうち、一番目と二番目の桁に０、１をそれぞれ書き込み、ＬＰＮを書き込む部分に０を書き込む(Ｓ４３３)。かつ、次の四つのデータＤ４、Ｄ５、Ｄ６及びＤ７を二番目のページ(ＰＰＮ=１)に順に書き込み(Ｓ４３２)、補助領域にＬＳＮ値として４、５、６及び７をそれぞれ書き込み、ＬＰＮ値として１を書き込む(Ｓ４３３)。
【００５２】
次に、Ｄ０及びＤ１を書き込む場合には、該当のＬＰＮ(「０」)が書き込まれたことがあるため(Ｓ４３０の例)、前記ＬＰＮを有するページ(ＰＰＮ=０)に空いているセクターが存在するかを判断する(Ｓ４４０)。ところで、空いているセクターが二つ存在するため、その空いているセクターにそれぞれＤ０、Ｄ１を書き込み(Ｓ４５０)、前記書き込んだＤ０、Ｄ１の位置に合わせて補助領域のＬＳＮを書き込む部分のうち、三番目及び四番目の桁に０、１をそれぞれ書き込む(Ｓ４８０)。
【００５３】
次に、Ｄ３を書き込む場合には、次の空いているページ(ＰＰＮ=２)の空いているセクター、即ち、一番目のセクターにＤ３を書き込み(Ｓ４５１)、該当のＬＳＮ(「３」)及び該当のＬＰＮ(「０」)を書き込む(Ｓ４６０)。次に、Ｄ１を書き込む場合には、Ｄ１を書き込む場合には、現在のページ(ＰＰＮ=２)に空いているセクターが存在するため(Ｓ３４０の例)、現在のページ(ＰＰＮ=２)の二番目のセクターにＤ１を書き込み(Ｓ４５０)、該当のＬＳＮを書き込む位置に１を書き込む(Ｓ４８０)。
【００５４】
五番目及び六番目として挙げられる方法は、ページマッピングを考慮しないセクターマッピング方法であり、ページの補助領域にＬＰＮを書き込む必要がない。図１５は、本発明による五つ番目の方法であって、オフセット一致セクターマッピング方法を示すフローチャートである。この方法は、セクターオフセットのみを維持し、空いているセクターを検索して書き込む方法である。
【００５５】
先ず、外部ホスト３００から作業を行いたい１つ以上のセクターのＬＳＮを入力される(Ｓ５１０)。次に、前記ＬＳＮからＬＰＮ及びＬＢＮを計算し、予め定義されているブロック単位のマッピング情報(mapping information)を用いてＰＢＮを決定する(Ｓ５２０)。前記決定されたＰＢＮに該当する物理ブロックに対し以下の過程を行う。先ず、現在のブロックセクターオフセットが一致し、次に、空いているセクターが存在するかを判断する(Ｓ５３０)。前記ステップＳ５３０での判断の結果、空いているセクターが存在すると、そのデータのオフセットが一致するセクターの位置にデータを書き込み(Ｓ５４０)、現在のページの補助領域のＬＳＮを書き込む部分のうち、該当の位置に当該のデータのＬＳＮを書き込み(Ｓ５５０)、終了する。前記Ｓ５３０での判断の結果、空いているセクターが存在しないと、新しいブロックを割り当てた後(Ｓ５３１)、ステップＳ５４０及びＳ５５０を行い、終了する。
【００５６】
図１６は、本発明によるオフセット一致セクターマッピング方法の実例を示す図である。先ず、Ｄ０及びＤ１を一番目のページ(ＰＰＮ=０)の一番目、二番目のセクターにそれぞれ書き込み(Ｓ５４０)、補助領域のＬＳＮを書き込む部分のうち該当の桁に０、１を書き込む(Ｓ５５０)。次に、Ｄ４、Ｄ５、Ｄ６及びＤ７を書き込む場合には、前記一番目のページ(ＰＰＮ=０)に四つのセクターを書き込む空間がないから、次のページ(ＰＰＮ=１)にそれぞれ書き込み(Ｓ５４０)、該当のＬＳＮである４、５、６及び７をそれぞれ書き込む(Ｓ５５０)。次に、Ｄ０、Ｄ１を書き込む場合には、Ｄ０、Ｄ１のオフセットのうち、空いているページ(ＰＰＮ=２)にＤ０、Ｄ１を書き込み(Ｓ５４０)、該当のＬＳＮである０、１をそれぞれ書き込む(Ｓ５５０)。
【００５７】
次に、Ｄ３を書き込む場合には、Ｄ３のオフセットのうち、空いているページ(ＰＰＮ=０)にＤ３を書き込み(Ｓ５４０)、該当のＬＳＮである３を書き込む(Ｓ５５０)。その後、Ｄ１を書き込む場合には、Ｄ１のオフセットのうち空いているページ(ＰＰＮ=３)にＤ１を書き込み(Ｓ５４０)、該当のＬＳＮである１を書き込む(Ｓ５５０)。
【００５８】
最終に、Ｄ６及びＤ７を書き込む場合には、Ｄ６及びＤ７のオフセットである三番目及び四番目のセクターが空いているページ(ＰＰＮ=２)にＤ６、Ｄ７を書き込み(Ｓ５４０)、該当のＬＳＮである６、７を書き込む(Ｓ５５０)。
図１７は、六番目の方法であって、オフセット不一致セクターマッピング方法を示すフローチャートである。この方法は、ページ及びセクターオフセットの何れにも拘らず、空いているセクターに順に書き込む方法である。
【００５９】
先ず、外部ホスト３００から作業を行いたい１つ以上のセクターのＬＳＮを入力される(Ｓ６１０)。かつ、前記ＬＳＮからＬＰＮ及びＬＢＮを計算し、予め定義されているブロック単位のマッピング情報(mapping information)を用いてＰＢＮを決定する(Ｓ６２０)。前記決定されたＰＢＮに該当する物理ブロックに対し以下の過程を行う。先ず、現在のブロックにてオフセットを考慮することなく、単に空いているセクターが存在するかを判断する(Ｓ６３０)。前記ステップＳ６３０での判断の結果、空いているセクターが存在すると、その空いているセクターにデータを書き込み(Ｓ６４０)、現在のページの補助領域のＬＳＮを書き込む部分のうち、該当の位置にそのデータのＬＳＮを書き込み(Ｓ６５０)、終了する。前記ステップＳ６３０での判断の結果、空いているセクターが存在しないと、新しいブロックを割り当てた後(Ｓ６３１)、ステップＳ６４０及びＳ６５０を行い、終了する。
【００６０】
図１８は、本発明によるオフセット不一致セクターマッピング方法の実例を示す図である。先ず、Ｄ０及びＤ１を一番目のページ(ＰＰＮ=０)の一番目、二番目のセクターにそれぞれ書き込み(Ｓ６４０)、補助領域のＬＳＮを書き込む部分のうち、該当の桁に０、１を書き込む(Ｓ６５０)。次に、Ｄ４、Ｄ５、Ｄ６及びＤ７を書き込む場合には、前記一番目のページ(ＰＰＮ=０)に四つのセクターを書き込む空間がないから、次のページ(ＰＰＮ=１)にこれをそれぞれ書き込み(Ｓ６４０)、該当のＬＳＮである４、５、６及び７をそれぞれ書き込む(Ｓ６５０)。次に、Ｄ０、Ｄ１を書き込む場合には、二つのセクターが空いている一番目のページ(ＰＰＮ=０)にＤ０、Ｄ１を書き込み(Ｓ６４０)、該当のＬＳＮである０、１をそれぞれ書き込む(Ｓ６５０)。
【００６１】
次に、Ｄ３を書き込む場合には、一番目のページ(ＰＰＮ=０)及び二番目のページ(ＰＰＮ=１)には、空いているセクターがないから、次のページ(ＰＰＮ=２)の一番目のセクターにＤ３を書き込み(Ｓ６４０)、該当のＬＳＮである３を書き込む(Ｓ６５０)。その後、Ｄ１を書き込む場合には、前記ページ(ＰＰＮ=２)の二番目のセクターにＤ１を書き込み(Ｓ６４０)、該当のＬＳＮである１を書き込む(Ｓ６５０)。最終に、Ｄ６及びＤ７を書き込む場合には、前記ページ(ＰＰＮ=２)に未だ二つのセクターが空いているから、そのページの三番目、四番目のセクターにＤ６、Ｄ７をそれぞれ書き込み(Ｓ６４０)、該当のＬＳＮである６、７を書き込む(Ｓ６５０)。
【００６２】
これまで、本発明によるマルチセクター書き込みが可能な大ブロックフラッシュメモリに効率よくデータを書き込む方法として、６つの方式を提案した。フラッシュメモリはページ単位のＩ/Ｏを許容しているため、多重セクター書き込み演算の場合には、フラッシュメモリのバッファを用いて各セクターをバッファリングした後、一度の演算で２つ以上のセクターへの書き込み演算を一度のフラッシュ書き込み演算で行うことができる。
【００６３】
このような書き込み方法に対応した読み出しアルゴリズムは、書き込みアルゴリズムの逆に行われる。一番目方法や二番目の方法のページマッピングにおいて、物理セクターオフセットは、論理アドレスのセクターオフセットと一致するため、読み出し要求されたセクターが位置したページを検索し、入力セクターのオフセットのデータを読み出すと良い。このとき、二番目の方法では、有効なページが一つ以上存在することがあるから、書き込みアルゴリズムの逆に最新のデータを検索することになる。
【００６４】
三番目や四番目の方法では、一旦、該当のページを検索した後、ＬＳＮを検索して該当のセクターを見付ける。このとき、同一のＬＳＮが２つ以上存在する場合には、書き込みアルゴリズムの逆に有効なセクターを検索する。
五番目の方法では、セクターオフセットが一致するため、書き込みアルゴリズムの逆に有効なセクターを見付けると良い。かつ、六番目の方法では、ＬＳＮ値から有効なセクターを見付けるが、このとき、同様に１つ以上のＬＳＮが存在する場合には、書き込みアルゴリズムの逆に有効なセクターを見付ければ良い。
【００６５】
［論理・物理マッピング情報管理方法］
以下に、論理・物理マッピング情報をフラッシュメモリに格納し、管理する方法の動作を説明する。本手法は、特に、大ブロックフラッシュメモリのみならず、小ブロックフラッシュメモリにも適用できることは言うまでも無い。
【００６６】
図１９（ａ）は、論理・物理マッピング情報を一定の大きさのセグメント(切れ)に分けたものを示す図である。１つのマップセグメントと１つの補助領域とをまとめた１つの単位をマップセグメントユニットと定義している。１つのマップセグメントの大きさは、フラッシュメモリのページの主領域の大きさと同様であっても良く、フラッシュメモリのページの主領域に複数のセグメントが存在しても良く、１つのセグメントがフラッシュメモリの複数のページの主領域に格納されても良い。マッピング情報の一部を更新する必要がある場合、全体のマッピング情報を何れも更新するのは、システムの性能を低下させることもあり、所定の大きさのセグメントにマッピング情報を分け、更新する必要のあるセグメントのみを更新することにする。
【００６７】
もし、図１９（ｂ）に示すように、マップセグメントの大きさがページの主領域の大きさと同じであるとし、１つのブロックに対する論理・物理マッピング情報に２Ｂが所要されるとするとき、小ブロックフラッシュメモリでは、１つのページ当たりに５１２Ｂの主領域を有することになり、１つのマップセグメントには２５６個のブロックに対するマッピング情報を格納することが可能となる。かつ、１つのブロックは、３２個のページを有することから、1つのマップブロックには３２個のマップセグメントユニットを格納することができる。従って、全体の論理・物理マッピング情報がＮ個のマップセグメントに分けて格納できるのであれば、３２-Ｎ個の空いているユニットが存在することになる。初期にＮ個のマップセグメントユニットが図１９（ａ）に示すように書き込まれている状態でマッピング情報の変更が発生したが、その変更は、マップセグメント#１で発生したとすれば、図１９（ｃ）に示すように、次の空いているユニットに変更されたマップセグメント#１を書き込めば良い。かつ、1つのブロック内にマップセグメント番号(#)の同じ複数のマップセグメントが存在すると、最後に書き込まれたマップセグメントのみが有効であると判断する。
【００６８】
それぞれのマップセグメントユニットは、マップセグメントの他に、マップセグメントに関する付加情報を有する補助領域を含んでいるが、小ブロックフラッシュメモリでは１６Ｂを使用することができる。前記論理・物理マッピング情報は、前述のように、ブロック単位のマッピング情報であっても良いが、これに限らず、セクター単位のマッピング情報であっても良く、大ブロックフラッシュメモリでのページ単位のマッピング情報であっても良いのはいうまでもない。即ち、前記論理・物理マッピング情報は、論理ブロック番号と物理ブロック番号との間のマッピング情報であっても良く、論理ページ番号と物理ページ番号との間のマッピング情報であっても良く、論理セクター番号と物理セクター番号との間のマッピング情報であっても良い。
【００６９】
図２０は、割り当てられたＭ個のマップブロックを示す図である。マップブロックは、データブロックとは別に所定の個数(Ｍ個)だけ割り当てて置き、ここに何れの論理・物理マッピング情報を書き込み可能にしている。書き込むマッピング情報の大きさが1つのブロックを超えないと(以下では、このような場合を仮定する)、1つのブロックのみ割り当てても動作が可能である。しかし、書き込みまたは消去作業を行う途中で突然電源が切れる可能性のあるシステムの場合には、新たに更新されるマッピングテーブルが完全に書き込まれるまで前のマッピングテーブルを消去せずに残して置くのが安全である。従って、２つ以上のブロックを割り当てて置けば、突然の電源の切断時にもマッピングテーブル情報を安全に管理することが可能となる。
【００７０】
図２１は、本発明によるマップセグメントユニット４００において、補助領域の構成を示す図である。前記補助領域(spare area)４２０には、論理・物理マッピング情報を安全に保護するための付加情報を書き込む。前記付加情報は、有効なマッピング情報に係るマップセグメントユニットを既存のマップブロックから新しいマップブロックにコピーするとき、番号を増加して書き込むエイジ(age)４２１、分けられて格納されたマップセグメントに関するシリアル番号を表示するセグメント番号(segment number)４２２、前記マップブロックを消去する途中でエラーがあったかどうかを知らせるシグネチャ(signature)４２３と、マップセグメントを書き込む途中でエラーが発生していなかったことを確認させる有効マーク(valid mark)４２４とから構成される。これらは、マップセグメントを格納するときに共に書き込まれる。
【００７１】
エイジ４２１は、複数のブロックのうち有効ブロックを検索するときに使用されるもので、ブロック当たり一度書き込めば良いが、本実施形態においては、実際にブロックの全てのマップセグメントユニットに書き込むことにしている。マッピング情報に係るマップセグメント４１０が更新される場合、ブロック内の一番目の空いているユニットに書き込み、更新されるマッピング情報に係るマップセグメント番号(segment number)４２２を共に書き込む。複数のマップセグメント４１０の更新により、それ以上ブロック内に空いているユニットが存在しない場合には、次の空いているマップブロックがあれば、そこに書き込み、空いているマップブロックがないと、有効でないマップブロックを消去した後、前のブロックの有効なマッピング情報に係るマップセグメント４１０を全て移動させ、新しいブロックには前のブロックのエイジ４２１よりも高いエイジ４２１を書き込む。従って、エイジ４２１の番号が最も大きいマップブロックが有効なことになる。
【００７２】
フラッシュメモリにおいて、前述のように、マッピング情報に係るマップセグメント４１０を更新する際に、有効なマップセグメント４１０を検索する方法は次のようになる。本発明では、有効なマッピング情報に係るマップセグメント４１０を有するブロックは、1つのみ存在することになる。従って、先ず、有効なマッピング情報を有するマップブロックを検索するようになるが、これは、マップブロックのうち、エイジ４２１が最も大きいブロックとなる。かつ、エイジ４２１が最も大きいマップブロックにも特定のセグメント番号４２２を有する複数のマップセグメント４１０が存在することがあるから、このうち、最も最近に(順次マップセグメントユニットを書き込んで行くときには一番下位に)書き込まれたマップセグメント４１０を選択すれば良い。
【００７３】
フラッシュメモリに書き込まれる一般のデータ情報は、一部が損失されても残りの部分だけでも使用者所望の作業を行うことができるが、これとは異なり、マッピング情報は、その情報量は少ないが、これが損失された場合、フラッシュメモリに格納された全体のデータが何れも無用になることもある。従って、マッピング情報を安全に保護するのは、極めて重要であると言える。特に、フラッシュメモリは、組み込み型システム(embedded system)またはモバイルデバイス(mobile device)などの応用に多く使用されており、突然の電源の切断に備える対策を必要としている。ところで、電源の切断が問題となる時点は、書き込み演算の途中または消去演算の途中で電源が切断されるときである。本発明では、電源の切断によって有効でなくなるデータを区別するために、シグネチャ(signature)４２３や有効マーク(valid mark)４２４という概念を導入している。即ち、マッピング情報に係るマップセグメント４１０を書き込んた後、常に有効マーク４２４を書き込むことによって、有効マーク４２４が書き込まれていないマップセグメント４１０は、最終まで完全に書き込まれていないとされ、有効でないマップセグメント４１０として見なされる。
【００７４】
また、マップセグメント４１０を書き込むときには、１つ以上のビット０を含む所定のバイトのシグネチャ４２３を共に書き込む。ブロックの消去演算が終了すると、ブロックの各ビットは、いずれも１に初期化される。従って、０に書き込まれていた各データが何れも１に変更されるが、消去する過程で電源が切れることになると、一部のビットは１と変更され、一部は０に残されることになる。従って、有効マーク４２４はそのまま残っていても、マップセグメント４１０を含むエイジ４２１、シグネチャ４２３などは変更されていることもある。このようになると、消去しようとしていたブロックのエイジ４２１が変更され、あいにく最も高いエイジ４２１を有するブロックに変更される可能性もある。例えば、消去する直前にマップブロックのエイジが二進数の「００００１０１」であったとすれば、マップブロックを消去する過程で前記「０」が「１」に変更され、「１１１１１１１」となり、有効なマップブロックのエイジ４２１よりも大きくなったとすれば、消去する過程を中断したマップブロックが最も大きいエイジ４２１を有する有効なマップブロックとして誤って認識されることもある。
【００７５】
しかし、ブロックの消去過程中で電源が切れ、エイジ４２１が変更されたときには、シグネチャ４２３のビットも１に変更されている可能性が高く、シグネチャが一致しない場合には、消去演算過程中で電源が切れたブロックとして見なすことで、前述した問題を解決することができる。消去演算過程中で電源が切れたかを確認するために、このような方法を用いる場合には、シグネチャの長さやシグネチャがビット０をどれだけ含んでいるかによって区別できる確率が異なることもある。
【００７６】
最終的に、マップブロック内に空いているユニットがない場合、新しいブロックに有効なマップセグメントユニット４００をいずれも移動させる作業が必要となるが、このとき、新しいブロックに有効なマップセグメントユニット４００を移動させる途中で電源が切れることになると、前のブロックが消去されておらず、二つのマップブロックに有効なマップセグメント４１０が共に存在することも可能である。しかし、本発明によると、新しいブロックにいずれの有効なマップセグメントユニット４００、エイジ４２１、セグメント番号４２２、及びシグネチャ４２３を完全に書き込んでから、有効マーク４２４を書き込むことになる。従って、新しいブロックにマップセグメントユニット４００を移動させる途中で電源が切れることになっても、有効なマップブロックを検索する過程で新しいマップブロックには有効マーク４２４が存在せず、エイジ４２１などによって最新のマッピング情報を有すると見られるマップブロックであっても有効でないと判断される。従って、このようなマップブロックは、有効なマップブロックを検索する過程で最初から除かれている。一方、前のマップブロックは、消去されずにそのまま残っており、これが有効なマップブロックとして選択される。従って、最新のマッピング情報は、安全に管理することが可能となる。
【００７７】
以上のように、上記実施の形態を参照して詳細に説明され図示されたが、本発明は、これに限定されるものではなく、このような本発明の基本的な技術的思想を逸脱しない範囲内で、当業界の通常の知識を有する者にとっては、他の多くの変更が可能であろう。また、本発明は、添付の特許請求の範囲により解釈されるべきであることは言うまでもない。
【図面の簡単な説明】
【００７８】
【図１】セクターマッピングの一例を示す図である。
【図２】従来のブロックマッピングの一例を示す図である。
【図３】フラッシュメモリが動作するシステムの全体構造を示すブロック図である。
【図４】従来のＮＡＮＤ型の小ブロックフラッシュメモリの構成を示す図である。
【図５】従来のＮＡＮＤ型の大ブロックフラッシュメモリの構成を示す図である。
【図６】大ブロックフラッシュメモリの読み出し・書き込み単位であるページの基本フォーマットを示す図である。
【図７】本発明による１対１ページマッピング過程を示すフローチャートである。
【図８】本発明による１対１ページマッピング方法の実例を示す図である。
【図９】本発明による１対ｎページマッピング過程を示すフローチャートである。
【図１０】本発明による１対ｎページマッピング方法の実例を示す図である。
【図１１】１対１ページマッピングを応用したセクターマッピング方法を示すフローチャートである。
【図１２】本発明による１対１ページマッピングを応用したセクターマッピング方法の実例を示す図である。
【図１３】本発明による１対ｎページマッピングを応用したセクターマッピング方法を示すフローチャートである。
【図１４】本発明による１対ｎページマッピング方法の実例を示す図である。
【図１５】本発明によるオフセット一致セクターマッピング方法を示すフローチャートである。
【図１６】本発明によるオフセット一致セクターマッピング方法の実例を示す図である。
【図１７】本発明によるオフセット不一致セクターマッピング方法を示すフローチャートである。
【図１８】本発明によるオフセット不一致セクターマッピング方法の実例を示す図である。
【図１９】（a）は、マップブロックとマップセグメントとの関係を示す図であり、（b）は、マップセグメントに格納された情報の例を示す図であり、（c）は、マップセグメントが変更された場合の動作を示す図である。
【図２０】割り当てられた所定数のマップブロックを示す図である。
【図２１】本発明によるマップセグメントユニットにおける補助領域の構成を示す図である。
【符号の説明】
【００７９】
３００…外部ホスト
３１１…ＸＩＰ可能メモリ
３１２…フラッシュメモリ
３１３…ＣＰＵ
４００…マップセグメントユニット
４１０…マップセグメント
４２０…補助領域
４２１…エイジ
４２２…セグメント番号
４２３…シグネチャ
４２４…有効マーク
【図１】
2005196736.tif 000003
【図２】
2005196736.tif 000004
【図３】
2005196736.tif 000005
【図４】
2005196736.tif 000006
【図５】
2005196736.tif 000007
【図６】
2005196736.tif 000008
【図７】
2005196736.tif 000009
【図８】
2005196736.tif 000010
【図９】
2005196736.tif 000011
【図１０】
2005196736.tif 000012
【図１１】
2005196736.tif 000013
【図１２】
2005196736.tif 000014
【図１３】
2005196736.tif 000015
【図１４】
2005196736.tif 000016
【図１５】
2005196736.tif 000017
【図１６】
2005196736.tif 000018
【図１７】
2005196736.tif 000019
【図１８】
2005196736.tif 000020
【図１９】
2005196736.tif 000021
【図２０】
2005196736.tif 000022
【図２１】
2005196736.tif 000023