(57)【要約】【課題】論理アドレスと物理アドレスとの対応関係を効率的に変更すること。【解決手段】一つの実施形態によれば、コントローラは、連続する第１の数の論理アドレスのそれぞれと第１の数の物理アドレスのそれぞれに１対１に対応付け、対応関係を更新する。対応関係を更新する処理は、第１更新と、第１更新の後に実行される第２更新とを含む。第１更新は、第１の数の論理アドレスのうちの第１論理アドレスに第２の数の物理アドレスのうちの第１物理アドレスを対応づける処理である。第２更新は、距離情報と先頭の論理アドレスに対応する物理アドレスを示す原点情報とに基づいて、第１の数の論理アドレスのうちの、第１論理アドレスから距離情報に応じた値だけ離れた第２論理アドレスを求め、第２論理アドレスに、第２の数の物理アドレスのうちの第２物理アドレスを対応付ける処理である。【選択図】図７
2019056981.tif 000002
【特許請求の範囲】
【請求項１】
ホストに接続可能なメモリシステムであって、
不揮発性の第１メモリと、
連続する第１の数の論理アドレスのそれぞれと前記第１の数の物理アドレスのそれぞれに１対１に対応付け、前記第１の数の物理アドレスは前記第１メモリの連続する第２の数の物理アドレスに含まれ、前記第２の数は前記第１の数よりも少なくとも１多く、前記第１の数の論理アドレスと前記第１の数の物理アドレスとの対応関係を更新するコントローラと、
距離情報および前記第１の数の論理アドレスのうちの先頭の論理アドレスに対応付けられた物理アドレスを示す原点情報が格納される第２メモリと、
を備え、
前記対応関係を更新する処理は、
前記第１の数の論理アドレスのうちの第１論理アドレスに前記第２の数の物理アドレスのうちの第１物理アドレスを対応づける第１更新と、
前記第１更新の後、前記原点情報と前記距離情報とに基づいて、前記第１の数の論理アドレスのうちの、前記第１論理アドレスから前記距離情報に応じた値だけ離れた第２論理アドレスを求め、前記第２論理アドレスに、前記第２の数の物理アドレスのうちの第２物理アドレスを対応付ける第２更新と、
を含み、
前記第２物理アドレスは、前記第１更新の実行前に前記第１論理アドレスに対応付けられていた物理アドレスである、
メモリシステム。
【請求項２】
前記対応関係を更新する処理は、前記第２更新を含む１以上の第３更新を含み、
前記第３更新は、
前記原点情報と前記距離情報とに基づいて、前記第１の数の論理アドレスのうちの第３論理アドレスを求め、前記第３論理アドレスに、前記第２の数の物理アドレスのうちの第３物理アドレスを対応付ける処理であり、
前記第３論理アドレスは第４論理アドレスから前記距離情報に応じた値だけ離れた論理アドレスであり、
前記第４論理アドレスは、前記第１の数の論理アドレスのうちの前回の更新の対象の論理アドレスであり、
前記第３物理アドレスは、前記前回の更新の前に前記第４論理アドレスに対応付けられていた物理アドレスである、
請求項１に記載のメモリシステム。
【請求項３】
前記コントローラは、
実行された更新の回数である第３の数をカウントし、
アクセス先を特定する場合、前記アクセス先を示す第５論理アドレスが更新されるまでに要する更新の回数である第４の数を、前記第５論理アドレスと前記距離情報とに基づいて演算し、前記第４の数が前記第３の数よりも大きい場合、前記第５論理アドレスに対応付けられた第４物理アドレスを前記第５論理アドレスと前記原点情報とに基づいて求め、前記第４の数が前記第３の数よりも小さい場合、前記第５論理アドレスと前記原点情報と前記距離情報とに基づいて前記第４物理アドレスを求める、
請求項２に記載のメモリシステム。
【請求項４】
前記コントローラは、
各第３更新において、前記第１の数に対し、前記原点情報の減算と、更新の実行毎の前記距離情報の加算と、を実行して第５の数を求め、前記第５の数を前記第２の数で除算した第１剰余を求め、前記第１剰余に基づいて前記第３論理アドレスを求め、
前記第５論理アドレスを前記距離情報で除算した商と第２剰余とを求め、前記商と前記第２剰余とに基づいて前記第４の数を求める、
請求項３に記載のメモリシステム。
【請求項５】
前記距離情報は前記第１の数の約数である、
請求項４に記載のメモリシステム。
【請求項６】
前記距離情報および前記第１の数は、２のべき乗である、
請求項５に記載のメモリシステム。
【請求項７】
前記コントローラは、前記第１の数に対し、前記原点情報の減算と、更新の実行毎の前記距離情報の加算と、を実行して第５の数を求め、前記第５の数を前記第２の数で除算した第１剰余を求め、前記第１剰余に基づいて前記第３論理アドレスを求める、
請求項２に記載のメモリシステム。
【請求項８】
前記コントローラは、前記第１の数の論理アドレスの全てにかかる対応関係の更新を完了した場合、前記原点情報を更新する、
請求項２に記載のメモリシステム。
【請求項９】
前記コントローラは、
前記第３論理アドレスが無効であるか否かを判定し、
前記第３論理アドレスが無効でない場合、第５物理アドレスが示す位置に格納されているデータを前記第３物理アドレスが示す位置に移動させ、前記第５物理アドレスは前記第３論理アドレスに前記第３物理アドレスが対応づけられる前に前記第３論理アドレスに対応付けられていた物理アドレスであり、
前記第３論理アドレスが無効である場合、前記データの移動を実行しない、
請求項２に記載のメモリシステム。
【請求項１０】
前記コントローラは、前記第１の数の論理アドレスの全てにかかる対応関係の更新を完了した場合、前記距離情報を更新する、
請求項３に記載のメモリシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本実施形態は、メモリシステムに関する。
【背景技術】
【０００２】
従来、不揮発性メモリを有するメモリシステムがある。メモリシステムは、ホストから論理アドレスが指定された場合、その論理アドレスに対応付けられた物理アドレスを求め、不揮発性メモリ内の当該物理アドレスが示す位置にアクセスする。特定の物理アドレスにアクセスが集中すると、その物理アドレスが示す位置が他の位置よりも疲弊することによって、不揮発性メモリの寿命が短くなる。これを防ぐために、論理アドレスと物理アドレスとの対応関係を随時変更する処理が実行される。この処理は、ウェアレベリングと称され得る。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】米国特許出願公開第２０１４／０１９５７２５号明細書
【特許文献２】米国特許出願公開第２０１１／０２３８８９０号明細書
【特許文献３】米国特許出願公開第２０１４／００８２３２３号明細書
【特許文献４】米国特許出願公開第２０１０／０２８１２０２号明細書
【特許文献５】米国特許出願公開第２０１６／０１４７４６７号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００４】
一つの実施形態は、論理アドレスと物理アドレスとの対応関係を効率的に変更することができるメモリシステムを提供することを目的とする。
【課題を解決するための手段】
【０００５】
一つの実施形態によれば、メモリシステムはホストに接続可能である。メモリシステムは、不揮発性の第１メモリと、コントローラと、第２メモリとを備える。コントローラは、連続する第１の数の論理アドレスのそれぞれと第１の数の物理アドレスのそれぞれに１対１に対応付け、第１の数の論理アドレスと第１の数の論理アドレスとの対応関係を更新する。第１の数の物理アドレスは第１メモリの連続する第２の数の物理アドレスに含まれる。第２の数は第１の数よりも少なくとも１多い。第２メモリは、距離情報および第１の数の論理アドレスのうちの先頭の論理アドレスに対応付けられた物理アドレスを示す原点情報が格納される。対応関係を更新する処理は、第１更新と、第１更新の後に実行される第２更新とを含む。第１更新は、第１の数の論理アドレスのうちの第１論理アドレスに第２の数の物理アドレスのうちの第１物理アドレスを対応づける処理である。第２更新は、原点情報と距離情報とに基づいて、第１の数の論理アドレスのうちの、第１論理アドレスから距離情報に応じた値だけ離れた第２論理アドレスを求め、第２論理アドレスに、第２の数の物理アドレスのうちの第２物理アドレスを対応付ける処理である。第２物理アドレスは、第１更新の実行前に第１論理アドレスに対応付けられていた物理アドレスである。
【図面の簡単な説明】
【０００６】
【図１】図１は、第１の実施形態のメモリシステムの構成を示す図である。
【図２】図２は、第１の実施形態のメモリセルアレイの構成を示す図である。
【図３】図３は、第１の実施形態のメモリセルアレイの一部領域の斜視図である。
【図４】図４は、第１の実施形態のメモリセルの電気特性を示す図である。
【図５】図５は、第１の実施形態のメモリセルアレイの回路図である。
【図６−１】図６−１は、第１の実施形態のウェアレベリングによる、マッピングの遷移の一例を示す図である。
【図６−２】図６−２は、第１の実施形態のウェアレベリングによる、マッピングの遷移の一例を示す図である。
【図６−３】図６−３は、第１の実施形態のウェアレベリングによる、マッピングの遷移の一例を示す図である。
【図７】図７は、第１の実施形態のウェアレベリングの手順を示すフローチャートである。
【図８】図８は、第１の実施形態の、論理アドレスを物理アドレスに変換する手順を示すフローチャートである。
【図９】図９は、第１の実施形態の、論理アドレスが更新されるターンを演算する手順を示すフローチャートである。
【図１０】図１０は、第３の実施形態の、論理アドレスが更新されるターンを演算する手順を示すフローチャートである。
【発明を実施するための形態】
【０００７】
以下に添付図面を参照して、実施形態にかかるメモリシステムを詳細に説明する。なお、これらの実施形態により本発明が限定されるものではない。
【０００８】
（第１の実施形態）
図１は、第１の実施形態のメモリシステムの構成を示す図である。メモリシステム１は、ホスト２と接続可能である。メモリシステム１とホスト２との間の通信路の規格は、特定の規格に限定されない。一例では、ＳＡＳ（Serial  Attached  SCSI）が採用され得る。
【０００９】
ホスト２は、例えばパーソナルコンピュータ、携帯情報端末、またはサーバなどが該当する。メモリシステム１は、ホスト２からアクセスコマンド（リードコマンドおよびライトコマンド）を受け付けることができる。各アクセスコマンドは、アクセス先を示す論理アドレスを含んでいる。論理アドレスは、メモリシステム１がホスト２に提供する論理アドレス空間内の位置を示す。
【００１０】
メモリシステム１は、メモリコントローラ１０と、ＲｅＲＡＭ（Resistive  Random  Access  Memory）２０と、を備えている。メモリコントローラ１０は、ホスト２とＲｅＲＡＭ２０との間のデータ転送を実行する。
【００１１】
ＲｅＲＡＭ２０は、アクセス回路２１およびメモリセルアレイ２２を備える。
【００１２】
アクセス回路２１は、メモリコントローラ１０からの指示に応じて、メモリセルアレイ２２に対し、データの書き込み、データの読み出し、およびデータのイレースを実行する回路である。アクセス回路２１は、例えば、ロウデコーダ、センスアンプ、電圧発生回路、カラムデコーダ、およびページレジスタを含む。
【００１３】
メモリセルアレイ２２は、データを保持可能な記憶領域を構成する。図２は、第１の実施形態のメモリセルアレイ２２の構成を示す図である。ただし、図２は、１つのメモリセルレイヤーのみを示している。
【００１４】
メモリセルアレイ２２は、一つの方向（第１方向）に沿って設けられた複数のビット線ＢＬと、第１方向に直交する他の方向（第２方向）に沿って設けられた複数のワード線ＷＬと、ビット線ＢＬとワード線ＷＬとの交点に設けられた複数のメモリセルＭＣを備えている。複数のメモリセルＭＣの集合体によって、マット（ＭＡＴ）２３と呼ばれる単位が構成される。
【００１５】
メモリセルＭＣの各々は、整流素子（ダイオード）と可変抵抗素子とを含んでいる。ダイオードのカソードはワード線ＷＬに接続され、ダイオードのアノードは可変抵抗素子を介してビット線ＢＬに接続されている。可変抵抗素子は例えば、ダイオード上に記録層、及び保護層が順次積層された構造を備えている。
【００１６】
メモリセルアレイ２２において同一行に配置された複数のメモリセルＭＣは同一のワード線ＷＬに接続され、同一列にある複数のメモリセルＭＣは同一のビット線ＢＬに接続されている。またワード線ＷＬ、ビット線ＢＬ、及びメモリセルＭＣは、第１、第２方向の両方に直交する第３方向（半導体基板表面に対する垂線方向）に沿って複数設けられる。つまりメモリセルアレイ２２は、メモリセルＭＣが三次元的に積層された構造を有している。三次元構造におけるメモリセルの各層は、メモリセルレイヤーと表記される。なお、図２は、１つのメモリセルレイヤーのみを示している。
【００１７】
メモリセルアレイ２２はマトリクス状に配置された（ｍ＋１）×（ｎ＋１）個のマット２３を備える。ｍ、ｎはそれぞれ１以上の自然数である。前述したようにマット２３の各々には複数のメモリセルＭＣが含まれ、これらはマトリクス状に配置されている。例えば１つのマット２３には、例えば１６本のワード線ＷＬと１６本のビット線ＢＬが含まれる。すなわち、１つのマット２３内には、（１６×１６）個のメモリセルＭＣが含まれる。また、メモリセルアレイ２２内には、１６×（ｍ＋１）本のビット線ＢＬが含まれ、１６×（ｎ＋１）本のワード線ＷＬが含まれる。同一行にある複数のマット２３（すなわちワード線ＷＬを共通にするマット２３）が、ブロックＢＬＫを構成する。このため、メモリセルアレイ２２は、ブロックＢＬＫ０〜ＢＬＫｎにより構成されている。以下、ブロックＢＬＫ０〜ＢＬＫｎを区別しない場合には、単にブロックＢＬＫと呼ぶ。
【００１８】
なお、１つのメモリセルレイヤーに含まれるマット２３の数は特定の数に限定されない。１つのメモリセルレイヤーは１つのマット２３のみを含んでいていてもよいし、複数のマット２３を含んでいてもよい。また、１つのマット２３内に含まれるメモリセルＭＣの数は、（１６×１６）個に限定されない。
【００１９】
図３は、メモリセルアレイ２２の一部領域の斜視図であり、上記構成のメモリセルアレイ２２が三次元的に構成された様子を示している。メモリセルアレイ２２は、半導体基板の基板面垂直方向（第３方向）に、複数積層（第１メモリセルレイヤー、第２メモリセルレイヤー、…）されている。本図によれば、ワード線ＷＬ／メモリセルＭＣ／ビット線ＢＬ／メモリセルＭＣ／ワード線ＷＬ／…の順に形成されているが、ワード線ＷＬ／メモリセルＭＣ／ビット線ＢＬの組が、層間絶縁膜を介在して積層されても良い。
【００２０】
図４を用いて上記メモリセルＭＣの電気特性について説明する。上述したようにメモリセルＭＣは、可変抵抗素子ＶＲの抵抗値に応じて低抵抗状態と高抵抗状態とを取り得る。メモリセルＭＣが低抵抗状態の場合、メモリセルＭＣはデータ値“１”を保持した状態と見なされる。メモリセルＭＣが高抵抗状態の場合、メモリセルＭＣはデータ値“０”を保持した状態と見なされる。低抵抗状態とは、例えば抵抗値が１ｋ〜１０ｋΩの場合をいう。また、高抵抗状態とは、例えば抵抗値が１００ｋ〜１ＭΩの場合をいう。
【００２１】
図５は、上記メモリセルアレイ２２の回路図であり、特に１つのメモリセルレイヤーにおける、図２の領域Ａ１に相当する領域を示している。本図に例示されるように、メモリセルアレイ２２中には、複数のマット２３間を通過するようにして、複数のビット線ＢＬとワード線ＷＬとが形成されている。
【００２２】
マット２３は、前述の通り１６本のビット線ＢＬと１６本のワード線ＢＬとを含む。また、上記したように、マット２３は（ｍ＋１）×（ｎ＋１）個だけある。つまり、あるブロックＢＬＫｉにはワード線ＷＬ（１６ｉ）〜ＷＬ（１６ｉ＋１５）が形成される。またあるブロックＢＬＫに含まれる複数のマット２３の各々には、ビット線ＢＬ（１６ｊ）〜ＢＬ（１６ｊ＋１５）が形成される。但しｉ＝０〜ｎ、ｊ＝０〜ｍである。
【００２３】
そして、ビット線ＢＬとワード線ＷＬとの交点には、それぞれメモリセルＭＣが形成されている。
【００２４】
アクセス回路２１は、メモリコントローラ１０から供給される物理アドレスに応じてワード線ＷＬおよびビット線ＢＬを選択する。そして、アクセス回路２１は、選択ワード線ＷＬ、非選択ワード線ＷＬ、選択ビット線ＢＬ、および非選択ビット線ＢＬのそれぞれに、対応する電圧を印加することで、選択ワード線ＷＬと選択ビット線ＢＬとの交点に位置するメモリセルＭＣの状態を参照したり変化させたりする。
【００２５】
なお、ＲｅＲＡＭ２０は、実施形態の不揮発性の第１メモリの一例である。不揮発性の第１メモリとしては、ＲｅＲＡＭ２０に代えて、他の任意の種類の半導体メモリが適用可能である。例えば不揮発性の第１メモリとしては、ＭＲＡＭ（Magnetoresistive  Random  Access  Memory）、またはＮＡＮＤ型のフラッシュメモリが適用可能である。
【００２６】
図１に説明を戻す。メモリコントローラ１０は、プロセッサ１１およびＳＲＡＭ（Static  Random  Access  Memory）１２を備える。
【００２７】
プロセッサ１１は、例えばＣＰＵ（Central  Processing  Unit）などの演算装置である。プロセッサ１１は、プログラムに従ってメモリコントローラ１０の種々の機能を実現する。プログラムは、例えばＲｅＲＡＭ２０に予め格納されている。プロセッサ１１は、メモリシステム１のスタートアップ時にＲｅＲＡＭ２０からＳＲＡＭ１２にロードする。プロセッサ１１は、ＳＲＡＭ１２にロードしたプログラムを実行する。
【００２８】
例えば、プロセッサ１１は、アクセスコマンドに含まれる論理アドレスをＲｅＲＡＭ２０内の位置を示す物理アドレスに変換する。
【００２９】
アクセスコマンドがライトコマンドの場合には、プロセッサ１１は、書き込みの指示と、ホスト２から送られてきたデータと、変換によって得られた物理アドレスとをＲｅＲＡＭ２０に送信する。
【００３０】
アクセスコマンドがリードコマンドの場合には、プロセッサ１１は、リードの指示と、変換によって得られた物理アドレスとをＲｅＲＡＭ２０に送信する。プロセッサ１１は、ＲｅＲＡＭ２０からメモリコントローラ１０にデータを受信すると、受信したデータをホスト２に送信する。
【００３１】
さらに、プロセッサ１１は、ウェアレベリングを実行する。ウェアレベリングは、特定のメモリセルＭＣにアクセスが集中することを防止するために、メモリセルアレイ２２内の各メモリセルＭＣにアクセスを分散させる処理である。具体的には、プロセッサ１１は、論理アドレスと物理アドレスとの対応関係（マッピング）を所定のタイミングで変更する。
【００３２】
図６−１〜図６−３は、第１の実施形態のウェアレベリングによる、マッピングの遷移の一例を示す図である。本図に示される例によれば、１つの論理領域内の８つの連続する論理アドレスLA0〜LA7と、１つの物理領域内の９つの連続する物理アドレスPA0〜PA8のうちの、８つの物理アドレスと、が対応付けられる。論理領域は、論理アドレス空間の一部または全部である。物理領域は、メモリセルアレイ２２が構成する記憶領域の一部または全部である。
【００３３】
なお、LAは論理アドレスを表し、LAの後に付された数字はアドレス値を示す。PAは物理アドレスを表し、PAの後に付された数字はアドレス値を示す。ここでは一例として、論理領域の先頭のアドレス値および物理領域の先頭のアドレス値はともにゼロであるとする。
【００３４】
また、論理アドレスの総数が8であり、物理アドレスの総数が9であるので、１つの物理アドレスは何れの論理アドレスにも対応づけられていない状態にある。何れの論理アドレスも対応づけられていない物理アドレスを、空白の（vacant）物理アドレスと表記する。なお、各矢印は、１つの論理アドレスとその論理アドレスに対応付けられた物理アドレスとの対を示す。論理アドレスLA0〜LA7は、８つの論理アドレスを含むので、各状態でのマッピングは、８つの対を含んでいる。
【００３５】
状態0では、論理領域の先頭の論理アドレスであるLA0には、物理アドレスPA0が対応付けられている。先頭の論理アドレスLA0に対応付けられた物理アドレスを、原点と表記する。状態0のマッピングでは、原点は物理アドレスPA0である。状態0では、先頭の論理アドレスLA0からiだけオフセットされた論理アドレスである論理アドレスLAi（ただし、iは0から7までの整数）には、原点からiだけオフセットされた物理アドレスである物理アドレスPAiが対応付けられている。このように、連続する全ての論理アドレスと連続する複数の物理アドレスとがリニアに対応付けられている状態を基本状態と表記する。
【００３６】
実施形態では、物理領域は、各物理アドレスが論理的にリング状に配置されたリングバッファと見なされる。即ち、物理領域の先頭の物理アドレスPA0と、物理領域の末尾の物理アドレスPA8とが隣接している、として扱われる。
【００３７】
したがって、iが0からNla-1までの全ての整数において、論理アドレスLAiと物理アドレスPA((Org+i)%Npa)とを対応付けるマッピングの状態は、基本状態に該当する。一例では、図６−３に示される状態8は、基本状態に該当する。
【００３８】
ここで、Orgは原点である。Nlaは論理アドレスの総数である。Npaは物理アドレスの総数である。つまり、本例ではNpaは9である。%は、剰余を演算する演算子である。つまり、a%bは、aをbで除算した剰余を意味する。
【００３９】
以降、本明細書では、物理領域の先頭の物理アドレスは、物理領域の末尾の物理アドレスと論理的に隣接していることして説明する。
【００４０】
なお、状態0および状態8に示されるように、基本状態では、論理領域の末尾の論理アドレス（ここでは論理アドレスLA7）が対応付けられた物理アドレスに後続する物理アドレスが、空白の物理アドレスに該当する。そして、空白の物理アドレスには原点の物理アドレスが後続する。
【００４１】
第１の実施形態では、マッピングを、論理アドレス毎に更新することで、基本状態（例えば図６−１の状態0）から、当該基本状態とは原点Orgが異なる次の基本状態（例えば図６−３の状態8）に遷移させる。原点Orgの移動量は、距離Dstとして予め設定される。ここでは一例として、原点Orgは、距離Dstだけアドレス値が小さくなる方向（即ち負方向）にシフトされる、としている。例えば図６−１〜図６−３の場合、距離Dstは4であり、原点Orgは物理アドレスPA0から負方向に４つ離れた物理アドレスPA5にシフトされている。
【００４２】
マッピングが基本状態から次の基本状態に至るまでの間、マッピングに含まれる、それぞれ論理アドレスと論理アドレスとの間の一対一の対応関係を示す複数の対は、逐次更新される。各対の更新の詳細については後述する。以降、ある論理アドレスにかかる対を更新することを、論理アドレスを更新する、と表記することがある。
【００４３】
ＳＲＡＭ１２は、プロセッサ１１がワーキングエリア、バッファ、またはキャッシュなどとして使用することが可能なメモリである。
【００４４】
特に、ＳＲＡＭ１２には、原点情報１２１、距離情報１２２、およびカウント情報１２３が格納される。原点情報１２１は、原点Orgを示す情報である。距離情報１２２は、原点Orgの移動量である距離Dstを示す情報である。カウント情報１２３は、対の更新の実行回数を示すカウント値Cntを示す情報である。ここでは、原点情報１２１には原点Orgが記録され、距離情報１２２には距離Dstが記録され、カウント情報１２３にはカウント値Cntが記録されていることとする。
【００４５】
続いて、第１の実施形態のメモリシステム１の動作を説明する。図７は、第１の実施形態のウェアレベリングの手順を示すフローチャートである。なお、本図に示される手順のスタート時においては、マッピングは基本状態にあり、カウント値Cntはゼロであることとする。
【００４６】
まず、プロセッサ１１は、原点Org、距離Dst、およびカウント値Cntに基づいて、更新の対象の論理アドレスLAtargetを演算する（Ｓ１０１）。プロセッサ１１は、次の式（１）に従って論理アドレスLAtargetを求める。
LAtarget=(Nla-Org+Dst*(Cnt+1))%Npa      （１）
【００４７】
前述したように、Nlaは、論理アドレスの総数であり、Npaは、物理アドレスの総数である。図６−１〜図６−３の例に従えば、Nlaは8であり、Npaは9である。
【００４８】
なお、プロセッサ１１は、ＳＲＡＭ１２内の原点情報１２１に記録された原点Orgを使用する。プロセッサ１１は、ＳＲＡＭ１２内の距離情報１２２に記録された距離Dstを使用する。プロセッサ１１は、ＳＲＡＭ１２内のカウント情報１２３に記録されたカウント値Cntを使用する。
【００４９】
続いて、プロセッサ１１は、論理アドレスLAtargetおよび原点Orgに基づいて論理アドレスLAtargetに対応する現在の物理アドレスである物理アドレスPAcurrentを演算する（Ｓ１０２）。基本状態では、先頭の論理アドレスからのオフセット量と、原点Orgからのオフセット量とは一致する。また、物理領域はリングバッファと見なされる。よって、プロセッサ１１は、下記の式（２）に従って物理アドレスPAcurrentを求めることができる。
PAcurrent=(LAtarget+Org)%Npa      （２）
【００５０】
続いて、プロセッサ１１は、論理アドレスLAtarget、原点Org、および距離Dstに基づいて物理アドレスPAnextを演算する（Ｓ１０３）。物理アドレスPAnextは、論理アドレスLAtargetが新たに対応付けられる予定の物理アドレスである。プロセッサ１１は、物理アドレスPAcurrentから距離Dstだけ負方向に離れた物理アドレスを、物理アドレスPAnextとして演算する。具体的には、プロセッサ１１は、下記の式（３）に従って物理アドレスPAnextを求めることができる。
PAnext=(LAtarget+Org-Dst)%Npa      （３）
【００５１】
続いて、プロセッサ１１は、物理アドレスPAcurrentが示す位置に格納されているデータを読み出して（Ｓ１０４）、読み出されたデータを物理アドレスPAnextが示す位置に書き込む（Ｓ１０５）。
【００５２】
Ｓ１０４およびＳ１０５の処理では、プロセッサ１１は、ホスト２から論理アドレスLAtargetによって参照されるデータを、物理アドレスPAcurrentから物理アドレスPAnextに移動させている。プロセッサ１１は、ＳＲＡＭ１２をデータの移動のためのバッファとして使用してもよい。
【００５３】
続いて、プロセッサ１１は、カウント値Cntをインクリメントする（Ｓ１０６）。プロセッサ１１は、カウント値Cntに1を加算し、加算によって得られた値でカウント情報１２３を更新する。
【００５４】
続いて、プロセッサ１１は、カウント値Cnt（即ちＳ１０６によって更新された後のカウント値Cnt）が論理アドレスの総数Nlaと一致するか否かを判定する（Ｓ１０７）。マッピングが基本状態を逸脱してから次に基本状態になるまでに、各対に対して１回の更新が実行される。よって、Ｓ１０７の処理は、マッピングが再び基本状態に戻ったか否かを判定する処理に該当する。
【００５５】
カウント値Cntが論理アドレスの総数Nlaと一致しない場合（Ｓ１０７、Ｎｏ）、処理がＳ１０１に移行し、他の対の更新が実行される。
【００５６】
カウント値Cntが論理アドレスの総数Nlaと一致する場合（Ｓ１０７、Ｙｅｓ）、プロセッサ１１は、原点Orgを、下記の式（４）に従って更新する（Ｓ１０８）。プロセッサ１１は、式（４）によって得られた値で原点情報１２１を上書きする。
Org=(Org-Dst)%Npa      （４）
【００５７】
続いて、プロセッサ１１は、カウント値Cntをゼロでリセットする（Ｓ１０９）。プロセッサ１１は、カウント情報１２３に、ゼロを上書きする。
【００５８】
なお、Ｓ１０６およびＳ１０９では、プロセッサ１１は、下記の式（５）を用いてカウント値Cntを更新してもよい。
Cnt=(Cnt+1)%Nla      （５）
【００５９】
Ｓ１０９の実行が完了すると、処理がＳ１０１に移行する。
【００６０】
Ｓ１０１からＳ１０７までの処理は、ループ処理を構成している。１回のループ処理によって、１回の更新が実行される。１回の更新では、１つの対が更新される。マッピングは、Nla回の更新が実行されることで、基本状態から次の基本状態に移行する。
【００６１】
下記に、Nla回の更新のうちの連続する2回の更新の間の関係を説明する。i回目の更新において求まる論理アドレスLAtarget、物理アドレスPAcurrent、およびPAnextを、LAtarget_i、PAcurrent_i、PAnext_iと表記することとする。まず、論理アドレスLAtargetに関しては、下記の式（６）に示される関係が成立する。
LAtarget_(i+1)=(LAtarget_i+Dst)%Npa      （６）
【００６２】
また、式（２）、式（３）、および式（６）によれば、下記の式（７）に示される関係が導出できる。
PAnext_(i+1)=(LAtarget_(i+1)+Org-Dst)%Npa
=(LAtarget_i+Org)%Npa
=PAcurrent_i      （７）
【００６３】
式（７）は、PAcurrent_iは、i回目の更新によって空白の物理アドレスとなり、その後、i+1回目の更新においてLAtarget_(i+1)が対応付けられることを意味する。つまり、論理アドレスLAtarget_(i+1)に新たに対応付けられる物理アドレスPAnext_(i+1)は、物理領域内で、物理アドレスPAcurrent_(i+1)から負方向に距離Dstだけ離れた物理アドレスであり、その物理アドレスは、i回目の更新において得られた物理アドレスPAcurrent_iと等しい。
【００６４】
また、式（６）によれば、i回目の更新における論理アドレスLAtarget_iから距離Dstに応じた値だけ離れた論理アドレスが、i+1回目の更新における論理アドレスLAtarget_(i+1)として選択される。より詳しくは、式（６）によれば、i回目の更新における論理アドレスLAtarget_iに距離Dstを加算して得られる値が被除数であり物理アドレスの総数Npaが除数である剰余演算によって、i+1回目の更新における論理アドレスLAtarget_(i+1)が演算される。よって、プロセッサ１１は、PAcurrent_iから正方向に距離Dstだけ離れた物理アドレスを、式（２）によって物理アドレスPAcurrent_(i+1)として求めることができるように、論理アドレスLAtarget_(i+1)を演算する。
【００６５】
このように、図７に示される手順によれば、PAcurrentが更新毎に物理領域内で正方向に距離Dstずつシフトされるように論理アドレスLAtargetが選択される。そして、各更新においては、論理アドレスLAtargetが、物理領域内でPAcurrentから負方向に離れた物理アドレスPAnextに対応付けられる。よって、各更新において、論理アドレスLAtargetに、前回の更新によって空白の物理アドレスとなった物理アドレスを対応付けることが可能である。
【００６６】
次に、図６−１〜図６−３を参照しながら、各回の更新の具体例について説明する。なお、前述したように、図６−１〜図６−３に示される例では、距離Dstとして4が設定されている。
【００６７】
状態0では、カウント値Cntがゼロであり、原点OrgがPA0（即ちゼロ）である。よって、式（１）に基づき、論理アドレスLA3が更新の対象の論理アドレスLAtarget_0として求まる。また、式（２）に基づき、論理アドレスLAtarget_0に対応する物理アドレスPAcurrent_0として物理アドレスPA3が求まる。また、式（３）に基づき、物理アドレスPAnext_0として、物理アドレスPA3から負方向に４つ離れた物理アドレスである物理アドレスPA8が求まる。論理アドレスLA3に、物理アドレスPA8が対応付けられ、その結果、マッピングは状態1に移行する。
【００６８】
状態1では、論理アドレスLA7が、論理アドレスLAtarget_1として求まる。論理アドレスLA7は、物理アドレスPAcurrent_0である物理アドレスPA3から正方向に４つ離れた物理アドレスであり物理アドレスPAcurrent_1である物理アドレスPA7に対応する論理アドレスである。また、物理アドレスPAnext_1として、物理アドレスPA7から負方向に４つ離れた物理アドレスである物理アドレスPA3が求まる。論理アドレスLA7に、物理アドレスPA3が対応付けられ、その結果、マッピングは状態2に移行する。
【００６９】
状態2では、論理アドレスLA2が、論理アドレスLAtarget_2として求まる。論理アドレスLA2は、物理アドレスPAcurrent_1である物理アドレスPA7から正方向に４つ離れた物理アドレスであり物理アドレスPAcurrent_2である物理アドレスPA2に対応する論理アドレスである。また、物理アドレスPAnext_2として、物理アドレスPA2から負方向に４つ離れた物理アドレスである物理アドレスPA7が求まる。論理アドレスLA2に、物理アドレスPA7が対応付けられ、その結果、マッピングは状態3に移行する。
【００７０】
状態3では、論理アドレスLA6が、論理アドレスLAtarget_3として求まる。論理アドレスLA6は、物理アドレスPAcurrent_2である物理アドレスPA2から正方向に４つ離れた物理アドレスであり物理アドレスPAcurrent_3である物理アドレスPA6に対応する論理アドレスである。また、物理アドレスPAnext_3として、物理アドレスPA6から負方向に４つ離れた物理アドレスである物理アドレスPA2が求まる。論理アドレスLA6に、物理アドレスPA2が対応付けられ、その結果、マッピングは状態4に移行する。
【００７１】
以降、同様の手順で、状態4において論理アドレスLA1に物理アドレスPA6が対応付けられ、状態5において論理アドレスLA5に物理アドレスPA1が対応付けられ、状態6において論理アドレスLA0に物理アドレスPA5が対応付けられ、状態7において論理アドレスLA4に物理アドレスPA0が対応付けられる。これらの更新の結果、マッピングは、状態8に示されるように、基本状態に戻る。
【００７２】
次に、論理アドレスを物理アドレスに変換する手順を説明する。プロセッサ１１は、例えば、メモリシステム１がホスト２からアクセスコマンドを受信した場合、アクセスコマンドに含まれる論理アドレスを物理アドレスに変換し、得られた物理アドレスが示す位置にアクセスする。アクセス位置として指定された論理アドレスを、論理アドレスLAaccessと表記する。また、論理アドレスLAaccessに対応する物理アドレスを、物理アドレスPAaccessと表記する。
【００７３】
図８は、第１の実施形態の、論理アドレスLAaccessを物理アドレスPAaccessに変換する手順を示すフローチャートである。
【００７４】
まず、プロセッサ１１は、論理アドレスLAaccessにかかる対が更新されるターンCturn1を演算する（Ｓ２０１）。ターンCturn1は、論理アドレスLAaccessにかかる対が更新される際のカウント値Cntである。換言すると、ターンCturn1は、マッピングが最後に基本状態にあった時から論理アドレスLAaccessにかかる対が更新されるまでに要する、マッピングに対して実行される更新の数を意味する。ターンCturn1の演算方法については後述する。
【００７５】
続いて、プロセッサ１１は、カウント値CntがターンCturn1より小さいか否かを判定する（Ｓ２０２）。プロセッサ１１は、カウント値CntをＳＲＡＭ１２に格納されているカウント情報１２３から読み出す。
【００７６】
カウント値CntがターンCturn1より小さいことは、論理アドレスLAaccessがまだ更新されていないことを意味する。カウント値CntがターンCturn1以上であることは、論理アドレスLAaccessが更新済みであることを意味する。
【００７７】
よって、カウント値CntがターンCturn1より小さい場合（Ｓ２０２、Ｙｅｓ）、プロセッサ１１は、論理アドレスLAaccessおよび原点Orgに基づいて物理アドレスPAaccessを演算する（Ｓ２０３）。具体的には、プロセッサ１１は、下記の式（８）に基づいて物理アドレスPAaccessを演算する。
PAaccess=(LAaccess+Org)%Npa      （８）
【００７８】
また、カウント値CntがターンCturn1より小さくない場合（Ｓ２０２、Ｎｏ）、プロセッサ１１は、論理アドレスLAaccess、原点Org、および距離Dstに基づいて物理アドレスPAaccessを演算する（Ｓ２０４）。具体的には、プロセッサ１１は、下記の式（９）に基づいて物理アドレスPAaccessを演算する。
PAaccess=(LAaccess+Org+Dst)%Npa      （９）
【００７９】
なお、プロセッサ１１は、Ｓ２０３およびＳ２０４において、ＳＲＡＭ１２内の原点情報１２１に記録されている原点Orgを使用する。また、プロセッサ１１は、Ｓ２０４において、ＳＲＡＭ１２内の距離情報１２２に記録されている距離Dstを使用する。
【００８０】
Ｓ２０３またはＳ２０４によって、論理アドレスLAaccessを物理アドレスPAaccessに変換する処理が完了する。
【００８１】
このように、プロセッサ１１は、対の更新毎に逐次更新されるカウント値Cntと、論理アドレスLAaccessにかかる対が更新されるターンCturn1との比較によって、原点Orgを用いて物理アドレスを求めるか、原点Orgと距離Dstとを用いて物理アドレスを求めるか、を決定する。
【００８２】
次に、論理アドレスLAaccessが更新されるターンCturn1を演算する手順（即ちＳ２０１の処理）を説明する。
【００８３】
式（６）によって明らかなように、論理アドレスLAtargetは、物理アドレスの総数Npaに至るまで、更新毎に正方向に距離Dstずつシフトせしめられる。よって、距離Dstで除算して得られる剰余が同一の値となる複数の論理アドレスは、連続して論理アドレスLAtargetとして選択される。剰余が同一の値である複数の論理アドレスのうちでは、各論理アドレスは、距離Dstで除算して得られる商に応じた順番で、論理アドレスLAtargetとして選択される。論理アドレスLAtargetが物理アドレスの総数Npa以上となる場合、別の剰余に属する論理アドレスが論理アドレスLAtargetとして選択される。
【００８４】
このように、図７に示される手順によれば、各論理アドレスLAtargetは、距離Dstで除算して得られる剰余および商に基づく順番で選択される傾向がある。第１の実施形態では、この傾向を利用することによって、ターンCturn1を演算する。
【００８５】
図９は、第１の実施形態の、論理アドレスLAaccessが更新されるターンCturn1を演算する手順の一例を示すフローチャートである。本図の説明では、特に説明がない限り、剰余は、距離Dstで除算した剰余を指すこととする。
【００８６】
まず、プロセッサ１１は、論理アドレスLAaccessの剰余Raccessを求める（Ｓ３０１）。この処理は、下記の式（１０）として表せる。
Raccess=LAaccess%Dst      （１０）
【００８７】
Ｓ３０１に続いて、プロセッサ１１は、剰余がRaccessと一致する全ての論理アドレスのうちの、論理アドレスLAaccessが更新されるターンCturn2を演算する（Ｓ３０２）。プロセッサ１１は、例えば、下記の式（１１）によってCturn2を求めることができる。なお、floor(a/b)は、aをbで除算した商を求める関数である。
Cturn2=floor(LAaccess/Dst)      （１１）
【００８８】
Ｓ３０２に続いて、プロセッサ１１は、カウント値の変数Ctmpをゼロでリセットする（Ｓ３０３）。そして、プロセッサ１１は、最初に更新される論理アドレスの剰余Rfirstを演算する（Ｓ３０４）。プロセッサ１１は、下記の式（１２）に基づいて剰余Rfirstを求めることができる。
Rfirst=(Nla+Dst)%Npa      （１２）
【００８９】
Ｓ３０４に続いて、プロセッサ１１は、変数RtmpにRfirstを代入する（Ｓ３０５）。そして、プロセッサ１１は、剰余Rtmpが剰余Raccessと一致するか否かを判定する（Ｓ３０６）。
【００９０】
剰余Rtmpが剰余Raccessと一致しない場合（Ｓ３０６、Ｎｏ）、プロセッサ１１は、Ｓ３０７〜Ｓ３１１において、距離Dstで除算した剰余がRtmpと一致する論理アドレスの数Ngrpを演算する。
【００９１】
具体的には、まず、プロセッサ１１は、論理アドレスの総数Nlaを距離Dstで除算した商Qtmpを演算する（Ｓ３０７）。即ち、プロセッサ１１は、下記の式（１３）に基づいて商Qtmpを演算する。
Qtmp=floor(Nla/Dst)      （１３）
【００９２】
続いて、プロセッサ１１は、論理アドレスの総数Nlaを距離Dstで除算した剰余Rtmp2を演算する（Ｓ３０８）。即ち、プロセッサ１１は、下記の式（１４）に基づいて剰余Rtmp2を演算する。
Rtmp2=Nla%Dst      （１４）
【００９３】
続いて、プロセッサ１１は、RtmpがRtmp2より小さいか否かを判定する（Ｓ３０９）。RtmpがRtmp2より小さい場合（Ｓ３０９、Ｙｅｓ）、プロセッサ１１は、Rtmp2に1を加算して得られる値をNgrpに代入する（Ｓ３１０）。RtmpがRtmp2より小さくない場合（Ｓ３０９、Ｎｏ）、プロセッサ１１は、Rtmp2をNgrpに代入する（Ｓ３１１）。
【００９４】
Ｓ３１０またはＳ３１１に続いて、プロセッサ１１は、CtmpにNgrpを加算し、加算によって得られた値をCtmpに代入する（Ｓ３１２）。
【００９５】
続いて、プロセッサ１１は、剰余Rnextを演算する（Ｓ３１３）。剰余Rnextは、次に論理アドレスLAtargetとして設定される論理アドレスを距離Dstで除算した剰余である。具体的には、プロセッサ１１は、下記の式（１５）に基づいて剰余Rnextを求めることができる。
Rnext=Rtmp-Nla%Dst-1      （１５）
【００９６】
続いて、プロセッサ１１は、Rtmpに剰余Rnextを代入し（Ｓ３１４）、処理がＳ３０６に移行する。
【００９７】
Ｓ３０６において、Rtmpが剰余Raccessに一致すると判定された場合（Ｓ３０６、Ｙｅｓ）、プロセッサ１１は、CtmpにCturn2を加算し、加算によって得られた値をCturn1に代入する（Ｓ３１５）。そして、ターンCturn1を演算する手順が完了する。
【００９８】
このように、プロセッサ１１は、論理アドレスLAtargetと距離Dstとに基づいて、論理アドレスLAaccessが更新されるターンCturn1を求めることができる。プロセッサ１１は、論理アドレスLAtargetとして設定される論理アドレスの数を剰余が同一の値になるグループごとに加算することによって、論理アドレスLAaccessが更新されるターンCturn1を求めることができる。
【００９９】
なお、以上の説明においては、論理領域の先頭および物理領域の先頭のアドレス値はともにゼロであるとした。論理領域の先頭または物理領域の先頭のアドレス値はゼロでなくてもよい。論理領域の先頭のアドレス値がゼロではない場合、論理領域内の各論理アドレスを先頭からのオフセット量で置き換えることで、上記したアルゴリズムが適用可能となる。同様に、物理領域の先頭のアドレス値がゼロではない場合、物理領域内の各物理アドレスを先頭からのオフセット量で置き換えることで、上記したアルゴリズムが適用可能となる。
【０１００】
また、以上の説明においては、空白の物理アドレスの数が1であるとした。空白の物理アドレスの数は2以上であってもよい。例えば、連続するn個（n>1）の物理アドレスが空白の物理アドレスとして設定される。そして、各更新において、連続するn個の論理アドレスがそれぞれ論理アドレスLAtargetとして選択され、n個の空白の物理アドレスのそれぞれがPAnextとして選択される。そして、各更新では、複数の論理アドレスLAaccessと複数の物理アドレスPAnextとがリニアに対応するように、対応付けられる。
【０１０１】
また、以上の説明においては、原点Orgは負方向に距離Dstだけ移動せしめられるとした。上述したアルゴリズムを変形することで、原点Orgは正方向に距離Dstだけ移動せしめられるように構成されてもよい。
【０１０２】
また、以上の説明においては、プロセッサ１１がマッピングの更新を行うこととして説明した。プロセッサ１１が行う処理のうちの一部または全部は、ハードウェア回路によって実行されてもよい。
【０１０３】
また、ＳＲＡＭ１２は、距離情報１２２、原点情報１２１、およびカウント情報１２３が格納される第２メモリの一例である。距離情報１２２、原点情報１２１、およびカウント情報１２３の一部または全部は、ＳＲＡＭ１２と異なるメモリに格納され得る。距離情報１２２、原点情報１２１、およびカウント情報１２３の一部または全部は、ＲｅＲＡＭ２０に格納されてもよい。距離情報１２２、原点情報１２１、およびカウント情報１２３の一部または全部は、プロセッサ１１内のレジスタなどに保持されてもよい。
【０１０４】
以上述べたように、第１の実施形態によれば、メモリコントローラ１０は、連続する複数の論理アドレスのそれぞれに物理アドレスを対応付ける。物理アドレスの総数は、論理アドレスの総数よりも少なくとも１つ多い。メモリコントローラ１０は、１回目の更新において、複数の論理アドレスのうちの１つの論理アドレスLAtarget_0に物理アドレスPAnext_0を対応付ける。そして、メモリコントローラ１０は、２回目の更新において、原点Orgおよび距離Dstに基づいて、論理アドレスLAtarget_0から距離Dstに応じた値だけ離れた論理アドレスLAtarget_1を求め、論理アドレスLAtarget_1に物理アドレスPAnext_1即ち物理アドレスPAcurrent_0を対応付ける。物理アドレスPAcurrent_0は、1回目の更新の前に論理アドレスLAtarget_0に対応付けられていた物理アドレスである。
【０１０５】
この構成により、マッピングを距離Dstだけシフトすることが可能となる。
【０１０６】
なお、１つの論理アドレスにアクセスが集中する場合、その論理アドレスに隣接する論理アドレスに対してもアクセス頻度が高くなる傾向がある。ここで、一例として、論理アドレスLA4からLA6の範囲にアクセスが集中し論理アドレスLA4からLA6の範囲に物理アドレスPA4からPA6の範囲がリニアに対応付けられている場合を考える。その場合において、原点のシフト量即ち距離Dstが1である場合、更新によって、論理アドレスLA4からLA6の範囲に、物理アドレスPA3からPA5の範囲が新たに対応付けられる。物理アドレスPA4および物理アドレスPA5は、更新後においてもアクセスが集中する論理アドレスの範囲に対応するため、物理アドレスPA4および物理アドレスPA5の位置の疲弊が促進される。これに対し、距離Dstとして例えば3が設定されると、論理アドレスLA4からLA6の範囲には、更新によって、物理アドレスPA1からPA3の範囲が新たに対応付けられる。即ち、アクセスが集中する論理アドレスの範囲に対応する物理アドレスの範囲が更新の前後で重ならない。従って、物理領域内の特定の位置の疲弊が促進されることが防止される。
【０１０７】
このように、距離Dstの設定値が、例えばアクセスが集中する範囲の幅よりも大きくなるように設定されることで、物理領域に対するアクセスを分散させることが可能である。よって、論理アドレスと物理アドレスとの対応関係を効率的に変更することが可能となる。
【０１０８】
また、上記の構成によれば、空白の物理アドレスが１つあればマッピングのシフトが可能であるので、物理領域のサイズを節約することが可能である。即ち、論理アドレスと物理アドレスとの対応関係を効率的に変更することが可能となる。
【０１０９】
また、第１の実施形態によれば、メモリコントローラ１０は、i回目の更新において、原点Orgおよび距離Dstに基づいて、論理アドレスLAtarget_iを求め、論理アドレスLAtarget_iに、物理アドレスPAnext_iを対応付ける。物理アドレスPAnext_iは、i-1回目の更新の前に論理アドレスLAtarget_(i-1)に対応付けられていた物理アドレスPAcurrent_(i-1)と等しい。
【０１１０】
この構成により、各更新において、論理アドレスLAtargetに、前回の更新によって空白の物理アドレスとなった物理アドレスを対応付けることが可能である。更新が繰り返し実行されることで、全ての論理アドレスに対応する物理アドレスを、距離Dstずつシフトすることが可能である。
【０１１１】
また、第１の実施形態によれば、メモリコントローラ１０は、更新が実行された回数をカウント値Cntとして保持する。メモリコントローラ１０は、アクセス先を示す論理アドレスLAaccessが更新されるまでに要する更新の回数であるターンCturn1を、論理アドレスLAaccessと距離Dstとに基づいて演算する。そして、ターンCturn1がカウント値Cntよりも大きい場合、メモリコントローラ１０は、論理アドレスLAaccessと原点Orgとに基づいて物理アドレスPAaccessを求める。ターンCturn1がカウント値Cntよりも小さい場合、メモリコントローラ１０は、論理アドレスLAaccessと原点Orgと距離Dstとに基づいて物理アドレスPAaccessを求める。
【０１１２】
この構成により、メモリコントローラ１０は、マッピングが次に基本状態に至る前であっても、アクセス対象の論理アドレスLAaccessを物理アドレスPAaccessに変換することが可能である。
【０１１３】
なお、ターンCturn1とカウント値Cntとが等しい場合の処理は、データの移動のタイミングと論理アドレスLAtarget_iに物理アドレスPAnext_iを対応づけるタイミングとの関係に応じて決まる。図７に示される手順のように、データの移動が完了した後にカウント値Cntが更新される場合においては、メモリコントローラ１０は、ターンCturn1とカウント値Cntとが等しい場合、論理アドレスLAaccessと原点Orgと距離Dstとに基づいて物理アドレスPAaccessを求める。
【０１１４】
なお、第１の実施形態によれば、メモリコントローラ１０は、式（１）に示されるように、論理アドレスの総数Nlaに対し、原点Orgの減算と、更新の実行毎の距離Dstの加算と、を行う。そして、メモリコントローラ１０は、論理アドレスの総数Nlaに対する加算および減算によって得られた値を物理アドレスの総数Npaで除算した剰余を論理アドレスLAtarget_iとして求める。また、メモリコントローラ１０は、図９に示されるように、アクセス先の論理アドレスLAaccessを距離Dstで除算した商（Cturn2）および剰余（Raccess）を求め、求めた商および剰余に基づいてターンCturn1を演算する。
【０１１５】
また、第１の実施形態によれば、メモリコントローラ１０は、論理領域内の全論理アドレスの更新を完了した場合、原点情報１２１に記録された原点Orgを更新する。
【０１１６】
この構成により、メモリコントローラ１０は、いったんマッピングが基本状態に至った後に、マッピングの更新を継続することが可能である。
【０１１７】
なお、以上の説明においては、メモリコントローラ１０は、いったんマッピングが基本状態に至った後、マッピングの更新を継続する、として説明した。メモリコントローラ１０は、マッピングが基本状態に至った後、ウェアレベリングを停止してもよい。メモリコントローラ１０は、マッピングが基本状態に至る前にウェアレベリングを停止してもよい。
【０１１８】
（第２の実施形態）
第１の実施形態では、Rtmpと論理アドレスの総数Nlaを距離Dstで除算した剰余Rtmp2との比較に基づいてNgrpが演算された（Ｓ３０７〜Ｓ３１１）。
【０１１９】
第２の実施形態では、論理アドレスの総数Nlaの約数が、距離Dstとして設定される。このように距離Dstが設定されることによって、論理アドレスの総数Nlaを距離Dstで除算した剰余Rtmp2がゼロになる。RtmpはRtmp2以上となることが明らかであるので、プロセッサ１１は、論理アドレスの総数Nlaを距離Dstで除算した商をNgrpとして設定することができる。即ち、Rtmpと論理アドレスの総数Nlaを距離Dstで除算した剰余Rtmp2を求める処理（Ｓ３０８）と、RtmpとRtmp2とを比較する処理（Ｓ３０９）と、を省略することが可能である。
【０１２０】
また、第１の実施形態では、プロセッサ１１は、Ｓ３１３において、論理アドレスの総数Nlaを距離Dstで除算した剰余を用いてRnextを演算した。論理アドレスの総数Nlaを距離Dstで除算した剰余はゼロとなるので、Ｓ３１３の処理が簡単になる。
【０１２１】
このように、第２の実施形態では、論理アドレスの総数Nlaの約数が、距離Dstとして設定される。この構成により、論理アドレスLAaccessを物理アドレスPAaccessに変換する処理がより簡単になる。
【０１２２】
（第３の実施形態）
第２の実施形態によれば、論理アドレスの総数Nlaの約数が、距離Dstとして設定される。第３の実施形態では、さらに、論理アドレスの総数Nlaおよび距離Dstがともに2のべき乗によって構成される。こうすることで、論理アドレスLAaccessが更新されるターンCturn1を演算する手順をビット演算によって実現することが可能になる。
【０１２３】
図１０は、第３の実施形態の、論理アドレスLAaccessが更新されるターンCturn1を演算する手順を示すフローチャートである。まず、プロセッサ１１は、下記の式（１６）を用いることによって、Lower_addr1を求める（Ｓ４０１）。ここで、「&」は、ビットアンド演算を示す演算子である。「<<」は、左方向へのシフトを示す演算子である。
Lower_addr=LAaccess&(1<<Log2(Dst))      （１６）
【０１２４】
式（１６）は、LAaccessの下位側の2ビットの値を取得する処理である。この処理によって求まるLower_addrは、第１の実施形態のRaccessに相当する。
【０１２５】
続いて、プロセッサ１１は、下記の式（１７）に基づき、Lower_addrをビット反転する（Ｓ４０２）。式（１７）に含まれる「/」は、ビット反転の演算子である。
Lower_addr=/Lower_addr      （１７）
【０１２６】
続いて、プロセッサ１１は、下記の式（１８）に基づき、Higher_addrを求める（Ｓ４０３）。ここで、「>>」は、右方向へのシフトを示す演算子である。
Higher_addr=LAaccess>>Log2(Dst)      （１８）
【０１２７】
式（１８）は、LAaccessの下位側の２ビットを切り落とす処理である。この処理によって求まるHigher_addrは、第１の実施形態のCturn2に相当する。
【０１２８】
続いて、プロセッサ１１は、下記の式（１９）に基づき、ターンCturn1を求める（Ｓ４０４）。ここで、「|」は、ビットオア演算を示す演算子である。
Cturn1=(Lower_addr<<(Log2(Nla)-Log2(Dst)))|Higher_addr      （１９）
【０１２９】
この式（１９）は、更新の回数を剰余毎に積算し、さらに、Cturn2を加算する処理を示している。Ｓ４０４の後、第３の実施形態のターンCturn1を演算する手順が完了する。
【０１３０】
このように、論理アドレスの総数Nlaおよび距離Dstがともに2のべき乗によって構成されることで、ビット演算のみによってターンCturn1を求めることが可能となる。
【０１３１】
（第４の実施形態）
第１〜第３の実施形態によれば、各更新において、データが移動せしめられる（Ｓ１０４、Ｓ１０５）。プロセッサ１１は、物理アドレスPAcurrentが無効な論理アドレスに対応付けられていることが分かっている場合には、Ｓ１０４およびＳ１０５をスキップしてもよい。
【０１３２】
例えば、メモリシステム１は、ホスト２から、論理アドレスを指定してその論理アドレスを無効にするコマンドを受信することができる。プロセッサ１１は、そのコマンドを受信すると、指定された論理アドレスを無効な論理アドレスとして記憶する。そして、プロセッサ１１は、Ｓ１０４の前に、論理アドレスLAtargetは無効な論理アドレスに該当するか否かを判定する。論理アドレスLAtargetは無効な論理アドレスである場合、Ｓ１０４およびＳ１０５をスキップする。
【０１３３】
プロセッサ１１は、無効な論理アドレスを、任意の方法で記憶し得る。一例では、プロセッサ１１は、無効な論理アドレスのリストを作成し、そのリストをＳＲＡＭ１２に格納する。プロセッサ１１は、ホスト２からコマンドによって無効な論理アドレスが通知される毎に、そのリストを更新する。プロセッサ１１は、リストに代えて、無効な論理アドレスを、テーブル、フラグ、など、任意の形式のデータによって記憶し得る。プロセッサ１１は、有効な論理アドレスのみを記憶することによって、無効な論理アドレスを特定してもよい。
【０１３４】
プロセッサ１１は、無効な論理アドレスをアクセス先としたリードをホスト２から要求された場合、ホスト２に対し、予め決められたルールに従って応答する。例えば、プロセッサ１１は、ホスト２に対し、無効な論理アドレスである旨を通知する。
【０１３５】
以上述べたように、第４の実施形態によれば、メモリコントローラ１０は、論理アドレスLAtargetが無効な論理アドレスであるか否かを判定する。メモリコントローラ１０は、論理アドレスLAtargetが無効な論理アドレスではない場合、物理アドレスPAcurrentに格納されているデータを物理アドレスPAnextに移動する。論理アドレスLAtargetが無効な論理アドレスである場合、メモリコントローラ１０は、データの移動をスキップする。
【０１３６】
この構成により、メモリコントローラ１０は、不要なデータの移動をスキップすることが可能である。
【０１３７】
なお、第４の実施形態は、第１〜第３の実施形態のメモリシステム１に適用され得る。
【０１３８】
（第５の実施形態）
距離Dstは、可変に構成され得る。プロセッサ１１は、全ての対の更新を完了した場合に、距離Dstを変更することができる。全ての対の更新を完了した場合とは、具体的には、カウント値Cntが論理アドレスの総数Nlaと一致すると判定したタイミングから次にＳ１０１の処理が実行されるまでの期間に対応する。
【０１３９】
一例では、メモリシステム１は、ホスト２から距離Dstを指定したコマンドを受信する。プロセッサ１１は、そのコマンドを受信すると、上述した期間に、距離情報１２２の内容を指定された距離Dstで上書きする。
【０１４０】
別の例では、メモリシステム１は、距離Dstの候補値の数列を例えばＳＲＡＭ１２に予め記憶する。プロセッサ１１は、上述した期間が到来する毎に、数列に記載された候補値で距離Dstを更新する。
【０１４１】
距離Dstの候補値の数列は、任意に構成され得る。例えば、論理アドレスの総数Nlaが16である場合に、「8,  4,  8,  2,  8,  4,  8,  1,  8,  4,  8,  2,  8,  4,  8...」のような数列が、ＳＲＡＭ１２に予め格納されている。プロセッサ１１は、この数列の要素を、この数列の先頭から順番に、距離Dstとして設定する。この数列を、第１の数列と表記する。
【０１４２】
第１の数列は、論理アドレスの総数Nlaの半分の値である8と、8のさらに半分の値である4と、4のさらに半分の値である2と、マッピングを１つだけずらすための値である1と、を含んでいる。よって、プロセッサ１１は、論理領域内の各論理アドレスに対し、種々の物理アドレスを対応付けることが可能である。また、第１の数列は、論理アドレスの総数Nlaを基準としてその半分の値である8を多く含んでいる。これにより、マッピングを論理アドレスの総数Nlaの半分の量だけシフトされる。よって、特定の範囲の論理アドレスにアクセスが集中する場合においても、物理領域に対するアクセスを効率的に分散させることが可能である。
【０１４３】
なお、上述した第１の数列は、一例である。数列「8,  4,  8,  2,  8,  4,  8,  9,  8,  4,  8,  2,  8,  4,  8...」、または数列「8,  4,  8,  10,  8,  4,  8,  9,  8,  4,  8,  10,  8,  4,  8...」も適用可能である。これらの数列は、第１の数列に含まれる要素のうち、小さい値（例えば1または2）に対し、半周期（即ち8）だけ加算して得られるものである。このように、シフト量が一定以上の値となるように距離Dstの候補値の数列を構成してもよい。
【０１４４】
なお、第５の実施形態は、第１〜第４の実施形態のメモリシステム１に適用され得る。
【０１４５】
（第６の実施形態）
第１〜第５の実施形態では、プロセッサ１１は、マッピングが基本状態になる毎に、カウント情報１２３に記録されたカウント値Cntをゼロでリセットし、原点情報１２１に記録された原点Orgを更新する。原点情報１２１は、マッピングが基本状態になる毎に更新されなくてもよい。また、カウント情報１２３は、マッピングが基本状態になる毎にゼロでリセットされなくてもよい。
【０１４６】
例えば、プロセッサ１１は、カウント値Cntに代えて、カウント値Cnt’をカウント情報１２３に記録する。カウント値Cnt’は、ウェアレベリングの開始以来に実行された更新の回数を示す値である。プロセッサ１１は、ウェアレベリングを最初に開始する時にカウント値Cnt’をゼロでリセットし、その後、更新毎にカウント値Cnt’をインクリメントする。プロセッサ１１は、マッピングが基本状態になってもカウント値Cnt’をリセットしない。また、プロセッサ１１は、カウント値Cnt’がゼロであった時（即ちウェアレベリングを最初に開始した時）の原点Orgである原点Org_initを原点情報１２１に記録する。
【０１４７】
その場合、プロセッサ１１は、カウント値Cntを、下記の式（２０）に従って取得することができる。
Cnt=Cnt’%Nla      （２０）
【０１４８】
また、プロセッサ１１は、原点Orgを、下記の式（２１）に従って取得することができる。
Org=(Org_init-(Dst*floor(Cnt’/Nla)))%Npa      （２１）
【０１４９】
なお、式（２１）は、距離Dstが固定値であることを前提としている。floor(Cnt’/Nla)の部分は、ウェアレベリングの開始以来にマッピングが基本状態になった回数を示し、(Dst*floor(Cnt’/Nla))の部分は、ウェアレベリングの開始以来の原点Orgの移動量の合計を示す。距離Dstが可変に構成される場合には、(Dst*floor(Cnt’/Nla))の部分が変形されることで、原点Org_initから原点Orgを演算することが可能である。
【０１５０】
このように、第１〜第５の実施形態で述べたアルゴリズムは、種々に変形され得る。
【０１５１】
（第７の実施形態）
第１〜第６の実施形態を構成するアルゴリズムは、剰余演算を含んでいる。プロセッサ１１は、剰余演算を他の演算方法で代用することが可能である。
【０１５２】
例えば、Ｓ１０１において、プロセッサ１１は、剰余演算に代えて、比較演算を用いてLAtarget_iを演算してもよい。具体的には、例えば、プロセッサ１１は、前回の論理アドレスLAtarget_(i-1)に距離Dstを加算する。そして、プロセッサ１１は、(LAtarget_(i-1)+Dst)とNpaとを比較する。(LAtarget_(i-1)+Dst)がNpaより小さい場合、プロセッサ１１は、(LAtarget_(i-1)+Dst)をLAtarget_iとして取得する。(LAtarget_(i-1)+Dst)がNpa以上である場合、プロセッサ１１は、(LAtarget_(i-1)+Dst-Npa)をLAtarget_iとして取得する。
【０１５３】
このように、第１〜第６の実施形態で述べたアルゴリズムを構成する演算処理は、種々の置き換えが可能である。
【０１５４】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０１５５】
１  メモリシステム、２  ホスト、１０  メモリコントローラ、１１  プロセッサ、１２  ＳＲＡＭ、２０  ＲｅＲＡＭ、２１  アクセス回路、２２  メモリセルアレイ、２３  マット、１２１  原点情報、１２２  距離情報、１２３  カウント情報。
【図１】
2019056981.tif 000003
【図２】
2019056981.tif 000004
【図３】
2019056981.tif 000005
【図４】
2019056981.tif 000006
【図５】
2019056981.tif 000007
【図６−１】
2019056981.tif 000008
【図６−２】
2019056981.tif 000009
【図６−３】
2019056981.tif 000010
【図７】
2019056981.tif 000011
【図８】
2019056981.tif 000012
【図９】
2019056981.tif 000013
【図１０】
2019056981.tif 000014