(57)【要約】【課題】ウェアレベリングの効率をさらに高めること。【解決手段】連続するアドレスのいずれかが割り当てられるとともに、アドレスが未割り当ての状態に設定される第１のメモリライン１１ｂ、…、１１ｅと、連続するアドレスのいずれかが割り当てられる第２のメモリライン１１ａとを有する物理メモリ１１を有し、書き込みアクセスが第１のメモリラインのいずれか又は第２のメモリラインのいずれかへの書き込みであるかをアドレスに基づいて判定し、第１のメモリライン１１ｂ、…、１１ｅそれぞれへの書き込み回数と第２のメモリライン１１ａへの書き込み回数とを計数し、書き込み回数の合計が閾値を超えた場合、未割り当ての状態の第１のメモリラインを利用して、第２のメモリライン１１ａに割り当てられているアドレスと、第１のメモリラインに割り当てられているアドレスとを入れ替える、記憶装置１０が提供される。【選択図】図１
2016170703.tif 000002
【特許請求の範囲】
【請求項１】
連続するアドレスのいずれかが割り当てられるとともに、前記アドレスが未割り当ての状態に設定される複数の第１のメモリラインと、前記連続するアドレスのいずれかが割り当てられる第２のメモリラインと、を有する物理メモリと、
前記物理メモリへの書き込みアクセスが、前記複数の第１のメモリラインのいずれか又は前記第２のメモリラインのいずれかへの書き込みであるかを、前記アドレスに基づいて判定する判定部と、
前記複数の第１のメモリラインそれぞれへの書き込み回数を示す複数の第１計数値と、前記第２のメモリラインへの書き込み回数を示す第２計数値とを計数する計数部と、
前記複数の第１計数値と前記第２計数値との合計が所定の閾値を超えた場合、前記未割り当ての状態に設定されている前記第１のメモリラインを利用して、前記第２のメモリラインに割り当てられている前記アドレスと、前記第１のメモリラインに割り当てられている前記アドレスとを入れ替える制御部と、
を有する、記憶装置。
【請求項２】
前記制御部は、前記アドレスの入れ替えにおいて、前記未割り当ての状態に設定されている前記第１のメモリラインに対して前記第２のメモリラインに割り当てられている前記アドレスを割り当て、該第１のメモリラインの次のラインに位置する前記第１のメモリラインに割り当てられている前記アドレスを前記第２のメモリラインに割り当て、該次のラインに位置する前記第１のメモリラインを前記未割り当ての状態に設定する
請求項１に記載の記憶装置。
【請求項３】
前記未割り当ての状態に設定された前記第１のメモリラインに対して前記第２のメモリラインに割り当てられる前記アドレスを割り当てた場合に、前記複数の第１のメモリラインの並び順に従って前記アドレスが連続するように、前記アドレスは割り当てられており、
前記制御部は、前記第２のメモリラインに割り当てられている前記アドレスを前記未割り当ての状態に設定されている前記第１のメモリラインに割り当てた場合に前記アドレスの連続性が維持されるかを判定し、該連続性が維持される場合に前記入れ替えを実施する
請求項２に記載の記憶装置。
【請求項４】
前記制御部は、前記複数の第１のメモリラインのうち最大の前記第１計数値に対応する前記第１のメモリラインに割り当てられている前記アドレスを前記入れ替えの対象とする
請求項１に記載の記憶装置。
【請求項５】
前記第２のメモリラインは、前記第１のメモリラインよりも耐久性が高い
請求項１〜４のいずれか１項に記載の記憶装置。
【請求項６】
前記制御部は、前記第１計数値に応じて、前記未割り当ての状態に設定されている前記第１のメモリラインに対し、該第１のメモリラインの次のラインに位置する前記第１のメモリラインに割り当てられている前記アドレスを割り当て、該次のラインに位置する前記第１のメモリラインを前記未割り当ての状態に設定する処理を実行する
請求項１に記載の記憶装置。
【請求項７】
コンピュータが、
連続するアドレスのいずれかが割り当てられるとともに、前記アドレスが未割り当ての状態に設定される複数の第１のメモリラインと、前記連続するアドレスのいずれかが割り当てられる第２のメモリラインと、を有する物理メモリについて、前記物理メモリへの書き込みアクセスが、前記複数の第１のメモリラインのいずれか又は前記第２のメモリラインのいずれかへの書き込みであるかを、前記アドレスに基づいて判定し、
前記複数の第１のメモリラインそれぞれへの書き込み回数を示す複数の第１計数値と、前記第２のメモリラインへの書き込み回数を示す第２計数値とを計数し、
前記複数の第１計数値と前記第２計数値との合計が所定の閾値を超えた場合、前記未割り当ての状態に設定されている前記第１のメモリラインを利用して、前記第２のメモリラインに割り当てられている前記アドレスと、前記第１のメモリラインに割り当てられている前記アドレスとを入れ替える
記憶装置の制御方法。
【請求項８】
記憶装置と、前記記憶装置にデータを書き込む情報処理装置とを含む情報処理システムであって、
前記記憶装置は、
連続するアドレスのいずれかが割り当てられるとともに、前記アドレスが未割り当ての状態に設定される複数の第１のメモリラインと、前記連続するアドレスのいずれかが割り当てられる第２のメモリラインと、を有する物理メモリと、
前記情報処理装置から前記物理メモリへの書き込みアクセスが、前記複数の第１のメモリラインのいずれか又は前記第２のメモリラインのいずれかへの書き込みであるかを、前記アドレスに基づいて判定する判定部と、
前記複数の第１のメモリラインそれぞれへの書き込み回数を示す複数の第１計数値と、前記第２のメモリラインへの書き込み回数を示す第２計数値とを計数する計数部と、
前記複数の第１計数値と前記第２計数値との合計が所定の閾値を超えた場合、前記未割り当ての状態に設定されている前記第１のメモリラインを利用して、前記第２のメモリラインに割り当てられている前記アドレスと、前記第１のメモリラインに割り当てられている前記アドレスとを入れ替える制御部と、
を有する、情報処理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、記憶装置、記憶装置の制御方法、及び情報処理システムに関する。
【背景技術】
【０００２】
情報処理分野では様々な場面で、電源の供給を停止しても記憶内容を保持し続ける不揮発性メモリが利用されている。不揮発性メモリとしてはＮＡＮＤ型フラッシュメモリが広く利用されている。また、最近ではＲｅＲＡＭ（Resistance Random Access Memory）、ＰＣＭ（Phase Change Memory）、ＳＴＴ（Spin Transfer Torque）−ＭＲＡＭ（Magnetoresistive Random Access Memory）などの高性能な不揮発性メモリも開発されている。
【０００３】
不揮発性メモリは、同じメモリライン（例えば、１６ＫＢや１２８ＫＢなどのサイズを有するブロック）に繰り返し書込みを行うと、メモリセルが劣化することにより読み書きができなくなる性質がある。そのため、複数のメモリラインをまとめたチップや、複数のチップをまとめたモジュール毎に、特定のメモリラインへの書き込みが集中しないように書き込み先を分散させ、各メモリラインの消耗度合いを平準化するウェアレベリング（Wear Leveling）と呼ばれる技術が提案されている。
【０００４】
例えば、メモリラインを特定する物理アドレスと、書き込み先を特定する論理アドレスとを対応付ける変換テーブルを利用してウェアレベリングを実現する方式（Table-based Wear Leveling：以下、ＴＢ方式）が提案されている。
【０００５】
ＴＢ方式では、メモリコントローラが、論理アドレスを指定した書き込み指示を受け、変換テーブルに基づいて論理アドレスを物理アドレスに変換し、その物理アドレスをもとに書き込み先となるメモリラインを特定し、メモリライン毎に書き込み回数をカウントする。そして、書き込み回数が多いメモリラインがある場合に、メモリコントローラが、そのメモリラインの物理アドレスに対応する論理アドレスと、書き込み回数が少ないメモリラインの物理アドレスに対応する論理アドレスとを入れ替える。
【０００６】
ＴＢ方式とは異なる例として、１つのメモリラインをギャップライン（データを書き込まないライン）に設定し、ギャップラインの位置を順次シフトさせることでウェアレベリングを実現する方式（Start Gap Wear Leveling：ＳＧ方式）が提案されている。ＳＧ方式は、初期状態として、物理アドレスの順に論理アドレスが割り当てられ、最後の物理アドレスにギャップラインが割り当てられることを前提とする。
【０００７】
ＳＧ方式では、メモリコントローラが、メモリライン全体の書き込み回数をカウントし、カウント数が一定回数になった場合にギャップラインの位置を１つ前の物理アドレスにシフトさせる。このとき、メモリコントローラは、シフト先のメモリラインにあるデータをギャップラインにコピーし、シフト先のメモリラインをギャップラインに設定する。なお、ＳＧ方式では、ギャップラインのシフト回数をもとにメモリコントローラが論理アドレスと物理アドレスとの対応関係を把握する。
【０００８】
なお、メモリライン全体を複数のリージョンに分け、リージョン単位でＳＧ方式を適用するなどのＳＧ方式の改良技術も提案されている。また、書き換え保証回数が異なる複数種類のメモリが共存する不揮発性メモリについて、該不揮発性メモリへの書き込みデータの信頼性を確保するための技術が提案されている。該技術は、書き換え保証回数が少ないメモリへの書き込み回数をパーティション単位でカウントし、その書き込み回数が所定回数を超えたとき、書き換え保証回数が多いメモリへデータを書き込むように制御を行う。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開２０１１−４４２０７号公報
【非特許文献】
【００１０】
【非特許文献１】Moinuddin K. Qureshi et al.,"Enhancing Lifetime and Security of PCM-Based Main Memory with Start-Gap Wear Leveling", MICRO 2009.
【非特許文献２】Lei Jiang et al., "LLS: Cooperative integration of wear-leveling and salvaging for PCM main memory", 2013 43rd Annual IEEE/IFIP International Conference on Dependable Systems and Networks.
【非特許文献３】Hongliang Yu and Yuyang Du, "Increasing Endurance and Security of Phase-Change Memory with Multi-Way Wear-Leveling", Computers, IEEE Transactions on Vol.63.
【発明の概要】
【発明が解決しようとする課題】
【００１１】
ＴＢ方式は、変換テーブルを利用するため、プロセス技術の微細化や積層技術の向上などにより記憶素子の集積度が向上しメモリサイズが大きくなると、これに伴って変換テーブルのサイズも大きくなる。そのため、変換テーブルが占めるメモリサイズが大きくなる上、論理アドレスから物理アドレスへの変換に時間がかかることが問題となる。
【００１２】
他方、ＳＧ方式は、変換テーブルを利用せず、シフト回数などをもとに計算で論理アドレスから物理アドレスへの変換ができるため、メモリサイズが大きくなってもＴＢ方式が有する上記問題は生じない。但し、ＳＧ方式は、ＴＢ方式と比べてウェアレベリングの効率（書き込み先の平準化の効果）が低い。上記のようにＳＧ方式の改良技術も提案されてはいるが、ウェアレベリングの効率について改善の余地が依然としてある。
【００１３】
本発明の目的は、ウェアレベリングの効率をさらに高めることが可能な記憶装置、記憶装置の制御方法、及び情報処理システムを提供することにある。
【課題を解決するための手段】
【００１４】
一つの態様によれば、連続するアドレスのいずれかが割り当てられるとともに、アドレスが未割り当ての状態に設定される複数の第１のメモリラインと、連続するアドレスのいずれかが割り当てられる第２のメモリラインと、を有する物理メモリと、物理メモリへの書き込みアクセスが、複数の第１のメモリラインのいずれか又は第２のメモリラインのいずれかへの書き込みであるかを、アドレスに基づいて判定する判定部と、複数の第１のメモリラインそれぞれへの書き込み回数を示す複数の第１計数値と、第２のメモリラインへの書き込み回数を示す第２計数値とを計数する計数部と、複数の第１計数値と第２計数値との合計が所定の閾値を超えた場合、未割り当ての状態に設定されている第１のメモリラインを利用して、第２のメモリラインに割り当てられているアドレスと、第１のメモリラインに割り当てられているアドレスとを入れ替える制御部と、を有する、記憶装置が提供される。
【発明の効果】
【００１５】
本発明によれば、ウェアレベリングの効率をさらに高めることができる。
【図面の簡単な説明】
【００１６】
【図１】第１実施形態に係る情報処理システムの一例を示した図である。
【図２】第２実施形態に係る演算装置及び記憶装置のハードウェアへの実装形態及びその変形例を示した図である。
【図３】第２実施形態に係る記憶装置のメモリコントローラ及びメモリモジュールの機能などを示したブロック図である。
【図４】第２実施形態の一変形例に係る記憶装置のメモリコントローラ及びメモリモジュールの機能などを示したブロック図である。
【図５】第２実施形態に係るメモリラインのシフト制御方法について説明するための図である。
【図６】第２実施形態に係るメモリラインの置換制御方法について説明するための第１の図である。
【図７】第２実施形態に係るメモリラインの置換制御方法について説明するための第２の図である。
【図８】第２実施形態に係るメモリモジュールが有する優先ラインの数について説明するための図である。
【図９】第２実施形態に係るメモリコントローラが実行する処理の流れを示した第１のフロー図である。
【図１０】第２実施形態に係るメモリコントローラが実行する処理の流れを示した第２のフロー図である。
【図１１】第２実施形態に係る技術の適用による効果を示した図である。
【発明を実施するための形態】
【００１７】
以下に添付図面を参照しながら、本発明の実施形態について説明する。なお、本明細書及び図面において実質的に同一の機能を有する要素については、同一の符号を付することにより重複説明を省略する場合がある。
【００１８】
＜１．第１実施形態＞
図１を参照しながら、第１実施形態について説明する。図１は、第１実施形態に係る情報処理システムの一例を示した図である。
【００１９】
第１実施形態は、複数のメモリラインを有する物理メモリへのデータ書き込み時に、各メモリラインへの書き込み回数をカウントし、カウント数に応じてアドレス（論理アドレス）とメモリラインとの対応関係を制御する技術に関する。また、第１実施形態は、複数のメモリラインを２種類のグループ（優先ラインのグループ、通常ラインのグループ）に分け、通常ラインのグループ内での制御と、グループを跨いだ制御とを組み合わせることで、ウェアレベリングの効率を向上する方法を提供する。以下、図１に示した情報処理システム５を例に、第１実施形態に係る技術について説明する。
【００２０】
図１に示すように、情報処理システム５は、記憶装置１０と、情報処理装置２０とを含む。記憶装置１０は、データを記憶するストレージ装置である。情報処理装置２０は、記憶装置１０に接続され、記憶装置１０へのデータの読み書き処理を実行する。
【００２１】
記憶装置１０は、物理メモリ１１、判定部１２、計数部１３、及び制御部１４を有する。物理メモリ１１は、例えば、ＮＡＮＤ型フラッシュメモリ、ＲｅＲＡＭ、ＰＣＭ、ＳＴＴ−ＭＲＡＭなどの不揮発性のメモリ素子を含むメモリモジュールである。なお、物理メモリ１１は、ＤＲＡＭ（Dynamic Random Access Memory）などの揮発性のメモリ素子をさらに含んでいてもよい。判定部１２、計数部１３、及び制御部１４は、物理メモリ１１を制御するメモリコントローラの要素である。
【００２２】
情報処理装置２０は、例えば、ＣＰＵ（Central Processing Unit）、ＤＳＰ（Digital Signal Processor）、ＭＰＵ（Micro Processing Unit）などのプロセッサを含む演算処理装置と、メインメモリなどの主記憶装置とを含んだサーバなどのコンピュータである。情報処理装置２０は、バスやネットワークなどを介して記憶装置１０と双方向にデータを転送できる。記憶装置１０は、ＣＰＵ、ＲＡＭ（Random Access Memory）、ＨＤＤ（Hard Disk Drive）などを有する独立したストレージ装置である。図１の例で、情報処理装置２０は、アドレスＡ、Ｂ、Ｃ、Ｄのうち、書き込み先となるアドレスを指定して物理メモリ１１へのデータの書き込みを要求する。アドレスＡ、Ｂ、Ｃ、Ｄは、論理アドレスの一例である。
【００２３】
物理メモリ１１は、第１のメモリライン１１ｂ、…、１１ｅ、及び第２のメモリライン１１ａを有する。第１のメモリライン１１ｂ、…、１１ｅと第２のメモリライン１１ａの書き換え耐性（耐久性）は同じであってもよいが、第２のメモリライン１１ａの耐久性が第１のメモリライン１１ｂ、…、１１ｅより高い方が好ましい。また、第１のメモリライン１１ｂ、…、１１ｅは不揮発性のメモリ素子で構成されるが、第２のメモリライン１１ａは揮発性又は不揮発性のメモリ素子で構成されうる。
【００２４】
第１のメモリライン１１ｂ、…、１１ｅは、連続するアドレスＡ、…、Ｄのいずれかが割り当てられるとともに、アドレスＡ、…、Ｄが未割り当ての状態に設定される。以下、アドレスＡ、…、Ｄが未割り当ての状態に設定されたメモリラインをギャップラインＧａｐと呼ぶ場合がある。第２のメモリライン１１ａは、連続するアドレスＡ、…、Ｄのいずれかが割り当てられる。図１の例で、第１のメモリライン１１ｂ、…、１１ｅは、それぞれ物理アドレスＰ１、…、Ｐ４で識別される。第２のメモリライン１１ａは、物理アドレスＰＸで識別される。
【００２５】
判定部１２は、物理メモリへの書き込みアクセスが、第１のメモリライン１１ｂ、…、１１ｅのいずれか又は第２のメモリライン１１ａのいずれかへの書き込みであるかをアドレスＡ、…、Ｄに基づいて判定する。つまり、判定部１２は、情報処理装置２０がアドレスＢを書き込み先に指定した場合、指定されたアドレスＢに対応するメモリラインがどれかを判定する。
【００２６】
計数部１３は、第１のメモリライン１１ｂ、…、１１ｅそれぞれへの書き込み回数を示す第１計数値ＣｎｔＰ１、…、ＣｎｔＰ４と、第２のメモリライン１１ａへの書き込み回数を示す第２計数値ＣｎｔＸとを計数する。
【００２７】
図１の例で、計数部１３は、第１のメモリライン１１ｂへの書き込み回数を計数するラインカウンタ１３ｂを用いて第１計数値ＣｎｔＰ１を計数する。同様に、計数部１３は、第１のメモリライン１１ｃ、…、１１ｅへの書き込み回数をそれぞれ計数するラインカウンタ１３ｃ、…、１３ｅを用いて第１計数値ＣｎｔＰ２、…、ＣｎｔＰ４を計数する。また、計数部１３は、第２のメモリライン１１ａへの書き込み回数を計数するラインカウンタ１３ａを用いて第２計数値ＣｎｔＸを計数する。
【００２８】
制御部１４は、第１計数値ＣｎｔＰ１、…、ＣｎｔＰ４と第２計数値ＣｎｔＸとの合計が所定の閾値Ｔｈを超えたかを判定する。該合計が閾値Ｔｈを超えた場合、制御部１４は、未割り当ての状態に設定されている第１のメモリラインを利用して、第２のメモリライン１１ａに割り当てられているアドレスと、第１のメモリラインに割り当てられているアドレスとを入れ替える。
【００２９】
図１（＃１）の例では、ＣｎｔＰ１、…、ＣｎｔＰ４、ＣｎｔＸの合計が閾値Ｔｈを超えたとき、Ｓ１のように、物理アドレスＰＸの第２のメモリライン１１ａにアドレス「Ａ」が割り当てられている。一方、物理アドレスＰ１に対応する第１のメモリライン１１ｂはギャップラインＧａｐに設定され、アドレスが未割り当ての状態にある。物理アドレスＰ２、Ｐ３、Ｐ４にそれぞれ対応する第１のメモリライン１１ｃ、１１ｄ、１１ｅには、それぞれアドレス「Ｂ」、「Ｃ」、「Ｄ」が割り当てられている。
【００３０】
この状態で、制御部１４は、第１のメモリライン１１ｂ（Ｐ１）に対して第２のメモリライン１１ａに割り当てられているアドレス「Ａ」を割り当てる（Ｓ２）。次に、制御部１４は、第１のメモリライン１１ｂ（Ｐ１）の次のラインに位置する第１のメモリライン１１ｃ（Ｐ２）に割り当てられているアドレス「Ｂ」を第２のメモリライン１１ａに割り当てる。次に、制御部１４は、第１のメモリライン１１ｃ（Ｐ２）をギャップラインＧａｐに設定し、アドレスが未割り当ての状態にする（Ｓ３）。
【００３１】
他方、ＣｎｔＰ１、…、ＣｎｔＰ４、ＣｎｔＸの合計が閾値Ｔｈを超えていない場合、制御部１４は、図１（＃２）に示すように、第１計数値ＣｎｔＰ１、…、ＣｎｔＰ４に応じて、第１のメモリライン１１ｂ、…、１１ｅの範囲でギャップラインＧａｐをシフトさせる。このシフトが発生する条件（シフト条件）としては、例えば、ＣｎｔＰ１、…、ＣｎｔＰ４、ＣｎｔＸの合計がシフト用閾値を超えた場合や、特定の第１のメモリラインに書き込みが集中した場合（第１計数値の分布に大きなピークが出た場合）などが適用されうる。
【００３２】
シフト条件を満たすと、制御部１４は、ギャップラインＧａｐに設定されている第１のメモリライン１１ｃに対し、その次に位置する第１のメモリライン１１ｄに割り当てられているアドレス「Ｃ」を割り当てる。そして、制御部１４は、第１のメモリライン１１ｄをギャップラインＧａｐに設定する。また、制御部１４は、シフトを実行した回数（シフト数）を保持する。
【００３３】
シフト数が０の際に第１のメモリライン１１ｂに割り当てられていたアドレス「Ａ」と、ギャップラインＧａｐが設定されていた第１のメモリライン１１ｃの物理アドレス「Ｐ２」と、シフト数とから、アドレスの割り当て状況が計算できる。
【００３４】
例えば、図１（＃２）の例で、シフト数が「２」であれば、ギャップラインＧａｐは２ライン分（つまり、Ｐ２→Ｐ１→Ｐ４）と移動し、第１のメモリライン１１ｄに設定されていることが分かる。また、第１のメモリライン１１ｂ、１１ｃ、１１ｅにそれぞれ割り当てられたアドレス「Ｄ」、「Ａ」、「Ｃ」も計算でき、アドレスと、第１のメモリライン１１ｂ、…、１１ｅとの関係を記した変換テーブルを用いずに済むため、ＴＢ方式よりも記憶容量を節約することができる。
【００３５】
上記のシフト処理を実行しても特定のメモリラインへの書き換えが集中する可能性はあるが、図１（＃１）に示した処理により上記のシフト処理とは独立してメモリラインへの割り当て制御が行われるため、ＳＧ方式に比べてウェアレベリングの効率が高くなる。つまり、１つのシフト法則に基づくギャップラインＧａｐのシフトを採用するＳＧ方式に比べ、これとは独立した法則に基づく図１（＃１）の割り当て制御が行われることで、書き換え対象の分散効果が高まり、ウェアレベリングの効率向上が期待できる。
【００３６】
また、第２のメモリライン１１ａに耐久性の高いメモリ素子を利用することで、第２のメモリライン１１ａに書き換え処理が集中した場合における耐性が向上する。このように耐久性の高いメモリ素子を利用し、第２のメモリライン１１ａに書き換え処理が集中するようにすれば、第１のメモリライン１１ｂ、…、１１ｅに対する負荷が下がるため、物理メモリ１１の耐久性・信頼性が高まる。
【００３７】
例えば、制御部１４が、複数の第１のメモリライン１１ｂ、…、１１ｅのうち最大の第１計数値に対応する第１のメモリラインに割り当てられているアドレスを入れ替えの対象とすれば、物理メモリ１１の耐久性・信頼性を高める効果が促進される。
【００３８】
なお、図１の例では、ギャップラインＧａｐに設定された第１のメモリライン１１ｂ、…、１１ｅに対して第２のメモリライン１１ａに割り当てられるアドレスを割り当てた場合に、第１のメモリライン１１ｂ、…、１１ｅの並び順に従ってアドレスＡ、…、Ｄが連続するように、アドレスＡ、…、Ｄが割り当てられている。この場合、ギャップラインＧａｐの位置によっては、図１（＃１）のＳ１からＳ３の入れ替え処理後、アドレスの並び順を整合させるための再割り当て操作が生じることがある。
【００３９】
そのため、制御部１４は、第２のメモリライン１１ａに割り当てられているアドレスをギャップラインＧａｐの位置に割り当てた場合にアドレスＡ、…、Ｄの連続性が維持されるかを判定し、該連続性が維持される場合に入れ替え処理を実施することが好ましい。図１（＃１）の例では、ギャップラインＧａｐの次の第１のメモリライン１１ｃに、アドレス「Ａ」に続くアドレス「Ｂ」が位置するタイミングで上記の入れ替え処理が実行されている。この場合、図１（＃１）に示すようにアドレスの並び順を維持したまま、最小限の割り当て操作でアドレスの入れ替え処理が完了する。
【００４０】
上記のように、第２のメモリライン１１ａを優先ラインとし、第１のメモリライン１１ｂ、…、１１ｅを通常ラインとして、通常ラインの範囲でのライン制御と、両ラインを跨ぐライン制御とを組み合わせることで、ウェアレベリングの効率向上が期待できる。また、優先ラインの耐久性を通常ラインより高めることで、物理メモリ１１の耐久性・信頼性をさらに高めることができる。さらに、優先ラインと通常ラインとを跨ぐライン制御を実施するタイミングをギャップラインＧａｐの位置に応じて適切に制御することで、処理負荷を低減することができる。
【００４１】
以上、第１実施形態について説明した。
＜２．第２実施形態＞
次に、第２実施形態について説明する。
【００４２】
第２実施形態は、複数のメモリラインを有する物理メモリへのデータ書き込み時に、各メモリラインへの書き込み回数をカウントし、カウント数に応じて論理アドレスとメモリラインとの対応関係を制御する技術に関する。また、第２実施形態は、複数のメモリラインを優先ラインのグループと通常ラインのグループとに分け、通常ラインのグループ内での制御と、グループを跨いだ制御とを組み合わせることで、ウェアレベリングの効率を向上する方法を提供する。
【００４３】
［２−１．ハードウェアへの実装］
第２実施形態に係る技術は、複数のメモリラインを有するメモリモジュールｍＭと、メモリモジュールｍＭのライン制御を実施するメモリコントローラｍＣとにより実現される。ここでは、メモリモジュールｍＭ、メモリコントローラｍＣをハードウェアへ実装する際の実装形態について説明する。図２は、第２実施形態に係る演算装置及び記憶装置のハードウェアへの実装形態及びその変形例を示した図である。
【００４４】
図２（＃１）には、第２実施形態に係る技術が適用可能なハードウェアの一例として、コンピュータに搭載される演算装置１０１及び記憶装置１０２を例示した。演算装置１０１は、例えば、ＣＰＵ、ＦＰＧＡ、ＧＰＵ（Graphics Processing Unit）などである。記憶装置１０２は、バスやネットワークなどを介して演算装置１０１と通信する。
【００４５】
演算装置１０１は、例えば、ＰＣＢ（Printed Circuit Board）１０１ａ上に、演算チップ１０１ｃを含むパッケージ１０１ｂを搭載した実装形態をとる。パッケージ１０１ｂ内や演算チップ１０１ｃ内には、キャッシュメモリなどのメモリチップを含みうる。メモリチップは物理メモリの一例である。ＰＣＢ１０１ａ上には、演算チップ１０１ｃを含むパッケージ１０１ｂとは異なるパッケージを搭載することもできる。
【００４６】
記憶装置１０２は、例えば、ＰＣＢ１０２ａ上に、メモリチップ１０２ｃを含むパッケージ１０２ｂを搭載した実装形態をとる。メモリチップ１０２ｃは、物理メモリの一例である。メモリチップ１０２ｃ内やパッケージ１０２ｂ内には、メモリチップ１０２ｃの動作を制御する制御チップ（演算回路）が設けられうる。ＰＣＢ１０２ａ上には、メモリチップ１０２ｃを含むパッケージ１０２ｂとは異なるパッケージを搭載することもできる。
【００４７】
図１（＃１）の例は、メモリモジュールｍＭ、メモリコントローラｍＣを記憶装置１０２に実装する形態を示している。例えば、メモリチップ１０２ｃがメモリモジュールｍＭとして機能し、パッケージ１０２ｂに搭載した制御チップがメモリコントローラｍＣとして機能する。この形態以外にも、例えば、図１（＃２）に示すような様々な実装形態をとりうる。
【００４８】
（Ａ）の形態は、演算装置１０１のパッケージ１０１ｂにメモリコントローラｍＣとして機能する制御チップを搭載し、ＰＣＢ１０１ａ上にメモリモジュールｍＭとして機能するメモリチップを含むパッケージを搭載した例である。（Ｂ）の形態は、演算チップ１０１ｃがメモリコントローラｍＣとして機能する例である。
【００４９】
（Ｃ）の形態は、記憶装置１０２のメモリチップ１０２ｃがメモリモジュールｍＭ及びメモリコントローラｍＣとして機能する例である。（Ｄ）の形態は、メモリチップ１０２ｃがメモリモジュールｍＭとして機能し、これとは別にパッケージ１０２ｂ上にメモリコントローラｍＣとして機能する制御チップを搭載した例である。（Ｄ）のような実装形態は、ＳｉＰ（System in Package）と呼ばれる。（Ｅ）の形態は、メモリチップ１０２ｃをメモリモジュールｍＭとして機能させ、ＰＣＢ１０２ａ上に、メモリコントローラｍＣとして機能する制御チップを含むパッケージ１０２ｂを搭載した例である。
【００５０】
第２実施形態に係る技術の適用範囲は上記の例に限定されないが、上記のような実装形態をとることで、ハードウェア資源による同技術の具現化が可能になる。
［２−２．機能ブロック］
次に、図３を参照しながら、メモリコントローラｍＣ及びメモリモジュールｍＭの機能について説明する。図３は、第２実施形態に係る記憶装置のメモリコントローラ及びメモリモジュールの機能などを示したブロック図である。なお、図３に例示したメモリコントローラ１１０は、メモリコントローラｍＣの一例である。また、メモリモジュール１３０は、メモリモジュールｍＭの一例である。
【００５１】
メモリコントローラ１１０は、要求保持部１１１、アドレス判定部１１２、ライン計算部１１３、Ｒ／Ｗ制御部１１４、カウンタ制御部１１５、ライン制御部１１６、ポインタ保持部１１７、及びテーブル保持部１１８を有する。
【００５２】
一方、メモリモジュール１３０は、ＨＥ（High Endurance）メモリ１３１、ＬＥ（Low Endurance）メモリ１３２、及びカウンタ１３３を有する。なお、ＨＥメモリ１３１は、ＬＥメモリ１３２に比べて書き換え耐性（耐久性）が高い。例えば、ＨＥメモリ１３１としては、ＤＲＡＭ、ＳＬＣ（Single Level Cell）、ＲｅＲＡＭが適用されうる。但し、両メモリ素子の耐久性が同じであっても、第２実施形態に係る技術を適用しうる。
【００５３】
図３の例では、ＨＥメモリ１３１に物理アドレスＰＸを有するメモリラインが設定されている。以下、ＨＥメモリ１３１のメモリラインを優先ラインと呼ぶ場合がある。ＬＥメモリ１３２には、物理アドレスＰ１、…、Ｐ４を有する複数のメモリラインが設定されている。以下、ＬＥメモリ１３２のメモリラインを通常ラインと呼ぶ場合がある。また、物理アドレスがＰｋ（ｋ＝１，…，４，Ｘ）のメモリラインをメモリラインＰｋと表記する場合がある。
【００５４】
カウンタ１３３は、ＨＥメモリ１３１及びＬＥメモリ１３２に設定されている各メモリラインへの書き込み回数をカウントする。以下、メモリラインＰＸへの書き込み回数をＣｎｔＸ、メモリラインＰ１、…、Ｐ４への書き込み回数をそれぞれＣｎｔ１、…、Ｃｎｔ４と表記する。つまり、ＣｎｔＸ、Ｃｎｔ１、…、Ｃｎｔ４はカウンタ１３３によるカウント値である。
【００５５】
要求保持部１１１は、メモリモジュール１３０への読み書き処理の最中に演算装置１０１から読み書き要求を受けた場合に、その読み書き要求を一時的に保持する。アドレス判定部１１２は、読み書き要求で指定された読み書き先の論理アドレスが、優先ラインに対応するか否かを判定する。このとき、アドレス判定部１１２は、テーブル保持部１１８が保持する変換テーブルを参照する。変換テーブルは、優先ラインと、論理アドレスとを対応付けるテーブルである。
【００５６】
アドレス判定部１１２は、判定結果をＲ／Ｗ制御部１１４に通知する。また、読み書き先の論理アドレスが優先ラインに対応しない場合、アドレス判定部１１２は、その論理アドレスをライン計算部１１３に通知する。ライン計算部１１３は、アドレス判定部１１２から通知された論理アドレスに対応する通常ラインを計算する。ライン計算部１１３は、計算結果をＲ／Ｗ制御部１１４に通知する。
【００５７】
Ｒ／Ｗ制御部１１４は、アドレス判定部１１２、ライン計算部１１３から受けた通知に基づいて読み書き先のメモリラインを特定し、特定したメモリラインに対する読み書き処理を実行する。読み出し処理の場合、Ｒ／Ｗ制御部１１４は、メモリラインから読み出したデータを演算装置１０１に送る。一方、書き込み処理の場合、Ｒ／Ｗ制御部１１４は、データを書き込んだメモリラインをカウンタ制御部１１５に通知する。
【００５８】
カウンタ制御部１１５は、カウンタ１３３を制御し、Ｒ／Ｗ制御部１１４から通知を受けたメモリラインのカウント値を増加させる。ライン制御部１１６は、各メモリラインに対する論理アドレスの割り当てを制御する。また、ライン制御部１１６は、各メモリラインのカウント値を監視し、通常ラインに関するカウント値の合計が予め設定された閾値を超えた場合、通常ラインに設定されたギャップラインをシフトさせる。このとき、ライン制御部１１６は、後述するシフト制御又は置換制御を実施する。
【００５９】
ライン制御部１１６は、シフト制御又は置換制御を実施した後、ライン計算部１１３が論理アドレスから物理アドレスを計算する際に参照する特定のメモリラインの位置を示すポインタ（Ｓｔａｒｔ、Ｇａｐ）を特定し、ポインタ保持部１１７に通知する。また、ライン制御部１１６は、置換制御を実施した後、テーブル保持部１１８が保持する変換テーブルを更新する。
【００６０】
以上、メモリコントローラｍＣ及びメモリモジュールｍＭの機能について説明した。なお、図４に示すように、カウンタ１３３をメモリコントローラ１１０に搭載してもよい。図４は、第２実施形態の一変形例に係る記憶装置のメモリコントローラ及びメモリモジュールの機能などを示したブロック図である。
【００６１】
［２−３．ライン制御方法］
ここで、メモリラインの制御に関する処理方法について説明する。
（２−３−１．通常ラインの更新操作）
まず、図５を参照しながら、通常ラインの更新操作であるシフト制御について説明する。上記の通り、このシフト制御の処理は、主にライン制御部１１６が実行する。図５は、第２実施形態に係るメモリラインのシフト制御方法について説明するための図である。
【００６２】
図５の例では、初期状態（シフト数＝０）で、論理アドレスＡ、Ｂ、Ｃ、Ｄが、メモリラインＰＸ、Ｐ１、Ｐ２、Ｐ３に割り当てられ、アドレスが未割り当てのメモリライン（ギャップライン）がメモリラインＰ４に設定されている。なお、論理アドレスの並び順はＡ→Ｂ→Ｃ→Ｄ（降順）に設定され、通常ラインについて物理アドレスの並び順はＰ１→Ｐ２→Ｐ３→Ｐ４（降順）に設定されているとする。
【００６３】
ポインタ保持部１１７は、初期状態で、通常ラインの先頭に位置するメモリラインＰ１に割り当てられた論理アドレスＢの位置（物理アドレス）を示すポインタＳｔａｒｔを保持する。また、ポインタ保持部１１７は、ギャップラインに設定されたメモリラインの位置（物理アドレス）を示すポインタＧａｐを保持する。なお、図中ではギャップラインの位置にＧａｐと表示する。図５に示すように、これらのポインタの組１１７ａは、ライン制御部１１６がシフト制御を実施する度に変化する。
【００６４】
シフト制御は、通常ラインの範囲（メモリラインＰ１、…、Ｐ４）で実施される。シフト制御の実施条件（シフト条件）を満たした場合、ライン制御部１１６は、ギャップラインを１つ前のラインに移動させる。例えば、ライン制御部１１６は、メモリラインＰ４に設定されていたギャップラインをメモリラインＰ３に移動させる。このとき、ライン制御部１１６は、移動先のメモリラインにあるデータを移動前のメモリラインにコピーし、移動先のメモリラインをギャップラインに設定する。
【００６５】
なお、図５の例でシフト数が３の場合のように、メモリラインＰ１にギャップラインが設定された状態でシフト制御を実施する場合、ライン制御部１１６は、最後に位置するメモリラインＰ４にギャップラインをシフトさせる。シフト制御が繰り返されると、図５に示すように、論理アドレスＡ、…、Ｄに対応する物理アドレスＰＸ、Ｐ１、…、Ｐ４は、ライン制御部１１６がシフト制御を実施する度に変化する。但し、優先ラインへの割り当ては、シフト制御によって変化しない。
【００６６】
（２−３−２．優先ラインの更新操作）
次に、図６及び図７を参照しながら、優先ラインの更新操作である置換制御について説明する。上記の通り、この置換制御の処理は、主にライン制御部１１６が実行する。図６は、第２実施形態に係るメモリラインの置換制御方法について説明するための第１の図である。図７は、第２実施形態に係るメモリラインの置換制御方法について説明するための第２の図である。
【００６７】
図６の例は、図５の例でシフト数が３の状態において置換制御の実施条件（置換条件）を満たした場合の置換制御を示している。置換条件は、通常ラインの合計カウント数（Ｃｎｔ１＋…＋Ｃｎｔ４）が予め設定された閾値Ｔｈを超えたことである（Ｓ１１）。置換条件を満たした場合、ライン制御部１１６は、通常ラインに関するカウント値のうち最大のカウント値ＣｎｔＭを特定する（Ｓ１２）。
【００６８】
そして、ライン制御部１１６は、ＣｎｔＭに対応するメモリラインに割り当てられていた論理アドレスを優先ラインに割り当て、優先ラインに割り当てられていた論理アドレスをギャップラインに割り当てる。さらに、ライン制御部１１６は、ＣｎｔＭに対応するメモリラインをギャップラインに設定する。例えば、ＣｎｔＭがＣｎｔ２の場合には置換制御はＳ１３ａのようになり、ＣｎｔＭがＣｎｔ３の場合にはＳ１３ｂのようになる。
【００６９】
ライン制御部１１６は、置換制御後の状態で、ポインタＳｔａｒｔ、Ｇａｐを更新し、シフト数をギャップラインの移動量分だけ調整する（Ｓ１４）。例えば、Ｓ１３ａの場合、置換制御により、優先ラインに割り当てられた論理アドレスがＡからＢに置換されている。そのため、ライン制御部１１６は、論理アドレスの差（この場合には１番目の論理アドレスから２番目の論理アドレスへの変化なので「１−２＝−１」の計算から−１）を移動量分とする。図６の例はシフト数が３の状態であったから、「１−３＝−２」の計算により、シフト数が２に調整される。
【００７０】
また、ライン制御部１１６は、変換テーブルを更新する。つまり、ライン制御部１１６は、優先ラインの物理アドレスＰＸと、新たに優先ラインに割り当てられた論理アドレス（Ｓ１３ａの場合はＢ、Ｓ１３ｂの場合はＣ）とを対応付けるように変換テーブルを更新する。ライン制御部１１６により更新されたポインタはポインタ保持部１１７により保持され、更新後の変換テーブルはテーブル保持部１１８により保持される。
【００７１】
なお、ここでは通常ラインの合計カウント数が閾値Ｔｈを超えた場合に優先ラインの更新操作を行う方法を例示したが、通常ラインと優先ラインの合計カウント数が閾値Ｔｈを超えた場合に同操作を行うように変形してもよい。
【００７２】
（実施タイミングについて）
図６の例では、優先ラインの論理アドレスをギャップラインに割り当て、ＣｎｔＭに対応するメモリラインの論理アドレスを優先ラインに割り当てることで、通常ラインの範囲における論理アドレスの並び順が維持される状態になっていた。しかし、置換制御を実施するタイミングによっては、図７に示すように、論理アドレスの並び順が乱れる場合（並び順エラー）がある。この場合、ライン制御部１１６は、図７（Ｓ１３ｃ）に示すように、論理アドレスの交換を繰り返し実施して正しい並び順に調整する。
【００７３】
但し、論理アドレスの交換を行う際に、置換対象のメモリラインにあるデータのコピーが生じるため、交換の回数を少なくすれば処理負担を減らすことができる。そのため、ライン制御部１１６は、置換条件を満たし、さらに、ギャップラインに優先ラインの論理アドレスを割り当てた状態で正しい並び順になる場合に置換制御を実施してもよい。
【００７４】
例えば、図６（Ｓ１３ａ）に示すように、ギャップライン（Ｐ１）の次のメモリライン（Ｐ２）に割り当てられた論理アドレス（Ｂ）が、優先ラインに割り当てられた論理アドレス（Ａ）の次の論理アドレス（Ｂ）に一致するときが好適な実施タイミングとなる。このようなタイミング調整を行うことで、置換制御の実施により図７に示すような並び順エラーが生じずに済むため、置換制御に伴う処理負担が軽減され、処理の高速化に寄与する。
【００７５】
（優先ラインの数について）
これまで、説明の都合上、優先ラインの数を１つとして説明してきたが、図８に示すように、複数の優先ラインが設けられていてもよい。図８は、第２実施形態に係るメモリモジュールが有する優先ラインの数について説明するための図である。この場合、ライン制御部１１６は、ＣｎｔＭに対応するメモリラインの置換に適した優先ラインを選択し、選択した優先ラインを対象に上述した置換制御を実施する。後述する処理フローは、優先ラインが複数の場合を考慮した処理の流れを示している。
【００７６】
［２−４．処理フロー］
図９及び図１０を参照しながら、メモリコントローラ１１０が実行する処理の流れについて説明する。図９は、第２実施形態に係るメモリコントローラが実行する処理の流れを示した第１のフロー図である。図１０は、第２実施形態に係るメモリコントローラが実行する処理の流れを示した第２のフロー図である。なお、図９及び図１０に示した処理は、電源断などの所定の終了条件を満たした場合に終了する。
【００７７】
（Ｓ１０１）要求保持部１１１は、演算装置１０１が発したメモリモジュール１３０への読み書きを要求する入出力命令を受け付ける。このとき、要求保持部１１１は、読み書き先の論理アドレスＬＡを取得する。また、要求保持部１１１は、メモリモジュール１３０が他の読み書き処理の最中である場合、受け付けた入出力命令を保持する。
【００７８】
（Ｓ１０２）アドレス判定部１１２は、要求保持部１１１が受け付けた入出力命令が優先ラインを対象とするか否かを判定する。例えば、アドレス判定部１１２は、テーブル保持部１１８が保持する変換テーブルを参照し、優先ラインの物理アドレスＰＸに対応する論理アドレスとしてＬＡが登録されているか否かを判定する。優先ラインを対象とする場合、処理はＳ１０３へと進む。一方、優先ラインを対象としない場合、処理はＳ１０４へと進む。
【００７９】
（Ｓ１０３）アドレス判定部１１２は、テーブル保持部１１８が保持する変換テーブルをもとに論理アドレスＬＡを物理アドレスＰＡに変換する。
（Ｓ１０４）ライン計算部１１３は、計算により、論理アドレスＬＡが割り当てられている通常ラインの物理アドレスＰＡを特定する。このとき、ライン計算部１１３は、パラメータＴＡ、ＴＧ（初期値：ＴＡ＝ＴＧ＝０）を利用する。
【００８０】
以下、通常ラインの総数をＮＬ、ギャップラインのポインタをＧａｐ、初期状態（シフト数が０の状態）で通常ラインの先頭に位置するメモリラインに割り当てられた論理アドレスの割り当て位置を示すポインタをＳｔａｒｔと表記する。例えば、図５の例でシフト数が４の場合、Ｇａｐが３（メモリラインＰ１の位置をポインタ０で表現した場合）、Ｓｔａｒｔが１となる。この例ではＮＬが４となる。
【００８１】
ライン計算部１１３は、「ＴＡ＝Ｓｔａｒｔ＋ＬＡ」を計算する。次に、ライン計算部１１３は、Ｓｔａｒｔ＞Ｇａｐであるか否かを判定する。Ｓｔａｒｔ＞Ｇａｐである場合、ライン計算部１１３は、「ＴＧ＝Ｇａｐ＋ＮＬ」を計算する。一方、Ｓｔａｒｔ≦Ｇａｐである場合、ライン計算部１１３は、「ＴＧ＝Ｇａｐ」とする。次に、ライン計算部１１３は、ＴＡ＞ＴＧであるか否かを判定する。ＴＡ＞ＴＧである場合、ライン計算部１１３はＴＡを１増加させる。次に、ライン計算部１１３は、「ＰＡ＝ＴＡ  ｍｏｄ  ＮＬ」を計算する。ｍｏｄは剰余演算を表す。
【００８２】
（Ｓ１０５）Ｒ／Ｗ制御部１１４は、Ｓ１０３又はＳ１０４で得られた物理アドレスＰＡに対するデータの読み書き処理を実行する。
（Ｓ１０６）カウンタ制御部１１５は、Ｓ１０５で実行された処理が書き込み処理か否かを判定する。書き込み処理である場合、処理はＳ１０７へと進む。一方、読み出し処理である場合、処理はＳ１０１へと進む。
【００８３】
（Ｓ１０７）カウンタ制御部１１５は、カウンタ１３３を制御し、物理アドレスＰＡをもつメモリライン（書き込み先ライン）に対応するカウンタ値を１増加させる。
（Ｓ１０８）カウンタ制御部１１５は、通常ラインに関するカウント値の合計（総書き込み回数ＮＷ）を１増加させる。
【００８４】
（Ｓ１０９）ライン制御部１１６は、ＮＷ＞ＴＷであるか否かを判定する。但し、ＴＷは予め設定された閾値である。ＴＷは、例えば、通常ラインの耐久性や実験結果などをもとに設定される。ＮＷ＞ＴＷである場合、処理はＳ１１０（図１０）へと進む。一方、ＮＷ≦ＴＷである場合、処理はＳ１０１へと進む。
【００８５】
（Ｓ１１０）ライン制御部１１６は、置換制御に適した優先ラインｐＬを特定する。つまり、ライン制御部１１６は、置換制御を実施した場合に図７に示すような並び順エラーが生じない優先ラインｐＬを特定する。
【００８６】
例えば、ライン制御部１１６は、対象の優先ラインに割り当てられた論理アドレスの次の論理アドレスと、ギャップラインの次に位置する通常ラインに割り当てられた論理アドレスが一致する場合に、その優先ラインを優先ラインｐＬとする（図６を参照）。なお、図８に示すように優先ラインが複数ある場合でも、Ｓ１１０で特定される優先ラインｐＬの数は高々１つである。
【００８７】
（Ｓ１１１）ライン制御部１１６は、Ｓ１１０で優先ラインｐＬが特定されたか否かを判定する。優先ラインｐＬが特定された場合、処理はＳ１１２へと進む。一方、優先ラインｐＬが特定されなかった場合、処理はＳ１１４へと進む。
【００８８】
（Ｓ１１２）ライン制御部１１６は、通常ラインに対応するカウント値Ｃｎｔ１、…、Ｃｎｔ４の中から最大のカウント値ＣｎｔＭを抽出する。
（Ｓ１１３）ライン制御部１１６は、ＣｎｔＭが優先ラインｐＬへの書き込み回数を示すカウント値より大きいか否かを判定する。ＣｎｔＭの方が大きい場合、処理はＳ１１４へと進む。一方、ＣｎｔＭの方が小さい場合、処理はＳ１１５へと進む。つまり、置換先の優先ラインｐＬの方により多くの書き込みが集中している場合には、優先ラインｐＬに対する置換制御が行われないようにする。
【００８９】
（Ｓ１１４）ライン制御部１１６は、シフト制御を実施する。つまり、ライン制御部１１６は、ギャップラインのシフト先にあるデータをシフト前のギャップラインにコピーし、ギャップラインをシフト先のメモリラインにシフトさせる（Ｌｉｎｅ（Ｇａｐ）＝Ｌｉｎｅ（Ｇａｐ−１））。また、ライン制御部１１６は、通常ラインへの総書き込み回数ＮＷを０にリセットし、シフト回数を示すパラメータＳｈｉｆｔを１増加させる。Ｓ１１４の処理が完了すると、処理はＳ１１９へと進む。
【００９０】
（Ｓ１１５）ライン制御部１１６は、優先ラインｐＬにあるデータをギャップラインにコピーする。つまり、ライン制御部１１６は、事実上、優先ラインｐＬに割り当てられていた論理アドレスをコピー先のギャップラインに対応するメモリライン（通常ライン）に割り当てる。但し、通常ラインに対する論理アドレスの割り当て関係はライン計算部１１３による計算で求められるため、テーブルなどへの登録などは生じない。
【００９１】
（Ｓ１１６）ライン制御部１１６は、ＣｎｔＭに対応するメモリラインにあるデータを優先ラインｐＬにコピーする。つまり、ライン制御部１１６は、事実上、ＣｎｔＭに対応するメモリラインに割り当てられていた論理アドレスを優先ラインｐＬに割り当てる。
【００９２】
（Ｓ１１７）ライン制御部１１６は、変換テーブルを更新する。Ｓ１１５の場合とは異なり、優先ラインｐＬに対する論理アドレスはライン計算部１１３による計算で求められないため、ライン制御部１１６は、置換制御による割り当て関係の変化を変換テーブルに反映させる。
【００９３】
（Ｓ１１８）ライン制御部１１６は、ＣｎｔＭに対応するメモリラインをギャップラインに設定し、シフト数Ｓｈｉｆｔを変更し、カウンタ１３３の全てのカウンタ値を０にリセットする。シフト数Ｓｈｉｆｔの変更は、図６（Ｓ１４）に示すように、優先ラインｐＬに割り当てられた論理アドレスの置換制御前後における順番の差に基づいて行われる。つまり、ライン制御部１１６は、置換制御前のシフト数Ｓｈｉｆｔに上記順番の差を加算して新たなシフト数Ｓｈｉｆｔとする。
【００９４】
（Ｓ１１９）ライン制御部１１６は、ポインタＧａｐ、Ｓｔａｒｔなどのパラメータを更新する。例えば、ライン制御部１１６は、「Ｇａｐ＝ＮＬ−１−（Ｓｈｉｆｔ  ｍｏｄ  ＮＬ）」を計算してポインタＧａｐを更新する。また、ライン制御部１１６は、「Ｓｔａｒｔ＝Ｉｎｔ（Ｓｈｉｆｔ／（ＮＬ−１））」を計算してポインタＳｔａｒｔを更新する。また、ライン制御部１１６は、Ｓｈｉｆｔ＞ＮＬ（ＮＬ−１）の場合、Ｓｈｉｆｔを０にリセットする。Ｓ１１９の処理が完了すると、処理はＳ１０１（図９）へと進む。
【００９５】
以上、メモリコントローラ１１０が実行する処理の流れについて説明した。
上記のように、通常ラインの範囲内でシフト制御を実施することで書き込み負荷が分散され、さらに、優先ラインの置換制御を実施することで、シフト制御をしてもなお特定の通常ラインへの書き込みが集中するような状況でも書き込み負荷が平準化される。つまり、第２実施形態に係る技術を適用することでウェアレベリングの効率が向上する。
【００９６】
上記のシフト制御は一定の規則に基づくギャップラインのシフトであるため、変換テーブルを利用せずにアドレス変換が実現される。一方、置換制御では優先ラインについて変換テーブルを利用するが、通常ラインを含めた全てのメモリラインに関する変換テーブルを保持する場合に比べて記憶容量が少なくて済む。つまり、第２実施形態によれば、ＳＧ方式に比べてウェアレベリングの効率向上が見込め、かつ、ＴＢ方式のように規模の大きな変換テーブルを保持せずに済む分だけ記憶容量を節約することが可能になる。
【００９７】
（効果）
図１１を参照しながら、上述した効果について説明を補足する。図１１は、第２実施形態に係る技術の適用による効果を示した図である。図１１の横軸は優先ラインへのアクセス集中度を示し、縦軸はウェアレベリングの性能（任意単位）を示す。
【００９８】
総ライン数をＮ、ＨＥメモリ１３１のライン数をＸ、ＬＥメモリ１３２に比べたＨＥメモリ１３１へのアクセス集中度（倍率）をａ（横軸）、シフト数をＳとした場合、書き込み回数はそれぞれ下記の式（１）〜式（３）でおよそ評価できる。式（１）のＭはＬＥメモリ１３２への書き込み回数であり、式（２）のＲはＨＥメモリ１３１への書き込み回数であり、式（３）のＴは総書き込み回数である。
【００９９】
【数１】
2016170703.tif 000003
【０１００】
【数２】
2016170703.tif 000004
【０１０１】
【数３】
2016170703.tif 000005
【０１０２】
Ｘが０の場合の書き込み回数Ｍ、ＴをそれぞれＭ0、Ｔ0（下記の式（４）及び式（５）を参照）とすると、性能の向上度を表す評価値Ｇは下記の式（６）で表現できる。図１１は、メモリライン全体に占める優先ラインの割合毎に、優先ラインへのアクセス集中度に対する性能を評価値Ｇで評価した結果である。図１１から分かるように、性能の向上効果は、優先ラインの割合とアクセス集中度とが相乗的に寄与する。
【０１０３】
【数４】
2016170703.tif 000006
【０１０４】
【数５】
2016170703.tif 000007
【０１０５】
【数６】
2016170703.tif 000008
【０１０６】
なお、変換テーブルのサイズについても簡単に言及する。メモリモジュール１３０全体のサイズをＮとし、各メモリラインのサイズをＬＳとすると、メモリラインの数ＮＬはＮ／ＬＳで与えられる。ＴＢ方式の場合、変換テーブルの大きさＴは「Ｔ＝２×ＮＬ×ｌｏｇ2（ＮＬ）」で与えられる。一方、第２実施形態の場合、ＨＥメモリ１３１のライン数をＭとすれば、変換テーブルの大きさＴは「Ｔ＝Ｍ×ｌｏｇ2（ＮＬ）」で与えられる。つまり、変換テーブルのサイズをＭ／（２×ＮＬ）に縮小することが可能になる。
【０１０７】
以上、第２実施形態について説明した。
【符号の説明】
【０１０８】
５  情報処理システム
１０  記憶装置
１１  物理メモリ
１１ａ  第２のメモリライン
１１ｂ、１１ｃ、１１ｄ、１１ｅ  第１のメモリライン
１２  判定部
１３  計数部
１３ａ、１３ｂ、１３ｃ、１３ｄ、１３ｅ  ラインカウンタ
１４  制御部
２０  情報処理装置
Ａ、Ｂ、Ｃ、Ｄ  アドレス
Ｇａｐ  ギャップライン
ＣｎｔＰ１、ＣｎｔＰ２、ＣｎｔＰ３、ＣｎｔＰ４  第１計数値
ＣｎｔＸ  第２計数値
ＰＸ、Ｐ１、Ｐ２、Ｐ３、Ｐ４  物理アドレス
Ｔｈ  閾値
【図１】
2016170703.tif 000009
【図２】
2016170703.tif 000010
【図３】
2016170703.tif 000011
【図４】
2016170703.tif 000012
【図５】
2016170703.tif 000013
【図６】
2016170703.tif 000014
【図７】
2016170703.tif 000015
【図８】
2016170703.tif 000016
【図９】
2016170703.tif 000017
【図１０】
2016170703.tif 000018
【図１１】
2016170703.tif 000019