(57)【特許請求の範囲】
【請求項１】
複数のスレッドが動作するプロセッサにおいて、
仮想空間アドレスを管理するページの論理アドレスと物理アドレスとを関連付けるエントリを含む第１テーブル及び前記第１テーブルから削除されたエントリの論理アドレスを含む第２テーブルと、
複数のスレッドのうち１つのスレッドがアクセスする論理アドレスを物理アドレスに変換する際に、実行中のプログラムによるアクセス対象となるページである対象論理アドレスに対応するエントリが、前記第１テーブルに存在するか否かを判定する第１判定部と、
前記対象論理アドレスに対応するエントリが前記第１テーブルに存在しないと判定されたときに、前記第２テーブルを参照し、前記対象論理アドレスが前記第２テーブルに存在しないときに、前記対象論理アドレスが前記プログラムの実行中に未だアクセス対象となったことがないと判定する第２判定部と、
前記対象論理アドレスが未だアクセス対象となったことがないと判定されたときに、前記対象論理アドレスに対応するエントリをページテーブルから前記第１テーブルに読み込む処理を、所定時間遅延させて、前記一つのスレッドを遅延させる遅延制御部と、
を含むことを特徴とするプロセッサ。
【請求項２】
前記遅延制御部における前記読み込む処理は、読み込む処理に係る要求データを退避領域に所定時間退避させてから、前記要求データを送付することを特徴とする請求項１に記載のプロセッサ。
【請求項３】
前記第１テーブルのエントリ数が当該第１テーブルに登録可能なエントリ数の上限数と一致しているときに、当該第１テーブルのエントリのうち最古に登録された最古エントリを削除し、前記最古エントリが示す論理アドレスを、前記第２テーブルに登録することを特徴とする請求項１又は２のいずれか１つに記載のプロセッサ。
【請求項４】
複数のスレッドが動作するプロセッサを有するコンピュータに、
複数のスレッドのうち１つのスレッドがアクセスする論理アドレスを物理アドレスに変換する際に、仮想空間アドレスを管理するページの論理アドレスと物理アドレスとを関連付けるエントリを含む第１テーブルに、実行中のプログラムによるアクセス対象となるページである対象論理アドレスに対応するエントリが存在するか否かを判定する第１判定手順と、
前記対象論理アドレスに対応するエントリが前記第１テーブルに存在しないと判定されたときに、前記第１テーブルから削除されたエントリの論理アドレスを含む第２テーブルを参照し、前記対象論理アドレスが前記第２テーブルに存在しないときに、前記対象論理アドレスが前記プログラムの実行中に未だアクセス対象となったことがないと判定する第２判定手順と、
前記対象論理アドレスが未だアクセス対象となったことがないと判定されたときに、前記対象論理アドレスに対応するエントリをページテーブルから前記第１テーブルに読み込む処理を、所定時間遅延させて、前記一つのスレッドを遅延させる遅延制御手順と、
を実行させることを特徴とする演算処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、仮想記憶を用いて記憶管理を行う技術に関する。
【背景技術】
【０００２】
仮想記憶を用いてプログラムを実行するプロセッサでは、メモリ管理装置（以下、ＭＭＵ（Memory Management Unit）という）が、仮想記憶における論理アドレスから物理アドレスへのアドレス変換を行う。ＭＭＵは、このアドレス変換を高速に行うため、一般に、アドレス変換バッファ（以下、ＴＬＢ（Translation Look-aside Buffer）という）を用いる。ＴＬＢは、記憶装置に格納されたページテーブルのキャッシュとしての機能を果たし、ＭＭＵによりページ分割された記憶領域の各ページの論理アドレスと物理アドレスとを対応付けるエントリを含む。そして、ＭＭＵは、ＴＬＢのエントリに基づいて、プログラムによりアクセス対象とされるページの論理アドレスを、物理アドレスに変換する。
【０００３】
ここで、ＴＬＢはプロセッサの内部に設置されるバッファであるため、高速なアクセスが可能である一方で、記憶可能なデータ量が少ない。このため、ＴＬＢは、限られた数のエントリしか含むことができない。その一方で、近年、プロセッサ上で同時実行できるスレッド数を増加させることにより、プロセッサの性能を向上させる技術が進歩している。このため、スレッド数の増加に合わせてＴＬＢエントリ数も増加させる必要があるが、一般的には、アクセス遅延を保ちつつＴＬＢエントリ数を増加させるのは難しいため、スレッドあたりのＴＬＢエントリ数は減少する。そうすると、各スレッドによるアクセス対象のページの論理アドレスに対応するエントリがＴＬＢに存在しないＴＬＢミスが起こる頻度が高くなり、ＴＬＢスラッシングが発生してしまう。
【０００４】
かかるＴＬＢミスが起きた場合の解決処理として、例えば、ＭＭＵは、ページテーブルから、アクセス対象となる論理アドレスに対応するエントリを読み出す。しかし、ページテーブルは、通常プロセッサの外部の記憶装置に格納されている。このため、ページテーブルからのエントリの読み出しは、多くの時間を必要とする。
【０００５】
そこで、ＴＬＢミスが起きた場合でも論理アドレスから物理アドレスへのアドレス変換を速やかに行うための技術として、次のような技術が提案されている。すなわち、ＭＭＵが、２段階のＴＬＢを備える。そして、ＭＭＵは、第１のＴＬＢにおいてＴＬＢミスが発生した場合でも、第２のＴＬＢにおいて対応するエントリがあれば、そのエントリによって物理アドレスへのアドレス変換を行う。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開平３−２５７６４３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかし、かかる技術では、２段階のＴＬＢを備えることでページテーブルへのアクセス頻度は減少するものの、第１のＴＬＢでＴＬＢミスが発生した場合には、第２のＴＬＢを参照するという冗長処理が依然として必要である。ここで、そもそも第１のＴＬＢで発生するＴＬＢミスの発生頻度自体がさらに減少すれば、ＭＭＵは、論理アドレスから物理アドレスへのアドレス変換を、さらに高速に行うことができる。
【０００８】
以上のような従来技術の問題点に鑑み、開示の技術は、ＴＬＢミスの発生頻度を減少させることにより、論理アドレスから物理アドレスへのアドレス変換を高速に行い、プログラムの実行時間を短縮することを目的とする。
【課題を解決するための手段】
【０００９】
開示の技術は、複数のスレッドが動作するプロセッサにおいて、複数のスレッドのうち１つのスレッドがアクセスする論理アドレスを物理アドレスに変換する際に、次の動作を実現する。すなわち、開示の技術は、仮想空間アドレスを管理するページの論理アドレスと物理アドレスとを関連付けるエントリを含むテーブルに、実行中のプログラムによるアクセス対象となるページである対象論理アドレスに対応するエントリが存在するか否かを判定する。また、開示の技術は、対象論理アドレスに対応するエントリがテーブルに存在しないと判定されたときに、対象論理アドレスがプログラムの実行中にアクセス対象となったことがあるか否かを判定する。そして、開示の技術は、対象論理アドレスが未だアクセス対象となったことがないと判定されたときに、対象論理アドレスに対応するエントリをページテーブルから第１テーブルに読み込む処理を、所定時間遅延させて、一つのスレッドを遅延させる。
【発明の効果】
【００１０】
開示の技術によれば、各スレッド間の進行速度が調整される。その結果、各スレッドにおいて同時にアクセス対象となる記憶領域が局所に集中する傾向が強くなり、同時にアクセス対象となるページ数が減少する。したがって、ＴＬＢミスの発生頻度が減少し、ＴＬＢスラッシングの発生が抑制されることとなり、論理アドレスから物理アドレスへのアドレス変換が高速に行われ、プログラムの実行時間の短縮が実現する。
【図面の簡単な説明】
【００１１】
【図１】ブロック割当て方式及びサイクリック割当て方式における、アクセス対象の記憶領域の説明図である。
【図２】ＳＩＭＤ又はＳＰＭＤにおける、アクセス対象の記憶領域の説明図である。
【図３】スレッドの進行速度の調整がない状態における、プログラム実行中におけるメモリバンド幅の測定結果のダイアグラムである。
【図４】スレッドの進行速度の調整を施した状態における、プログラム実行中におけるメモリバンド幅の測定結果のダイアグラムである。
【図５】記憶管理機構を含んだ計算機システムの一実施例のブロック図である。
【図６】ＭＭＵ制御部の動作を示すフローチャートである。
【発明を実施するための形態】
【００１２】
まず、仮想記憶を用いたプログラムの実行時における、ＴＬＢスラッシング発生の仕組みについて説明する。
近年、コンピュータのプロセッサコアの動作周波数が飛躍的に向上した結果、動作周波数が物理的に実現可能な上限に到達してきており、さらなる動作周波数の向上が困難となってきている。このため、他の方法によりプロセッサの性能を向上させるべく、プロセッサコア数を増やすことでプロセッサ性能を向上させるマルチコアが一般的に採用されている。また、さらに他の方法として、１つのプロセッサコア上で複数スレッドを同時実行するＳＭＴ（Simultaneous Multi-threading Technology）等の採用も進んでいる。そして、かかるマルチコア化、ＳＭＴ化の進展により、プロセッサ上で同時実行されるスレッド数は増加する傾向にある。なお、同時実行されるスレッド数が多いプロセッサとして、例えばＧＰＵ（Graphic Processing Unit）等が挙げられる。
【００１３】
そして、同時実行されるスレッド数が多いプロセッサでは、多数のスレッドが、同時に記憶装置にアクセスする。このため、ＭＭＵは、多数のスレッドについて、同時にＴＬＢを用いて、論理アドレスから物理アドレスへのアドレス変換を行うこととなる。しかし、ＴＬＢが含むことのできるエントリ数には上限がある。このため、同時実行されるスレッド数が多い場合、同時にアクセス対象となるページ数が、ＴＬＢに含まれるエントリ数を上回る可能性が高くなる。そうすると、ＴＬＢミスが起こる頻度が高くなり、ＴＬＢスラッシングが発生してしまう。
【００１４】
そこで、ＴＬＢスラッシングを回避する方法としては、同時にアクセス対象となるページ数を少なくすることが有効である。そして、同時にアクセス対象となるページ数を少なくするには、アクセス対象となる記憶領域を、できる限り局所に集中させて分散させないようにすることが有効である。
【００１５】
ここで、アクセス対象となる記憶領域を局所に集中させる方法の１つとして、記憶領域の割当て方式を工夫する方法がある。一般に、連続したデータ領域を複数のスレッドが同時に並行してアクセスする場合、各スレッドに担当・処理させる記憶領域を割当てる方式として、ブロック割当て方式及びサイクリック割当て方式がある。ブロック割当て方式は、各スレッドに対し、記憶領域をスレッド数で等分したまとまった領域を割当てる方法である。一方、サイクリック割当て方式は、各スレッドに、小さな記憶領域を周期的に割当てる方式である。
【００１６】
図１は、以下に示すコードで記述されたプログラムを、４つのスレッドを用いてデータ並列で処理した場合において、ある特定のループ処理の実行時に、４つのスレッド（スレッド０〜スレッド３）によって同時にアクセス対象となる記憶領域を示したものである。
【００１７】
【数１】
0005428617.tif 000002
【００１８】
なお、図１において、「ａ１」で示すメモリ空間は、上記コードにおける配列ａ１に対応し、「ａ２」は、上記コードにおける配列ａ２に対応する。
そして、図１から明らかなように、ブロック割当て方式の場合、各スレッドによるアクセス領域が分散するため、同時にアクセス対象となるページ数が多くなる。一方、サイクリック割当て方式の場合、各スレッドによるアクセス領域が局所に集中する。このため、同時にアクセス対象となるページ数が少なくなる。このように、ブロック割当て方式よりもサイクリック割当て方式のほうが、同じプログラムを同じスレッド数で実行した場合において、同時にアクセス対象となるページ数が少ない。このため、サイクリック割当て方式を採用することが、ＴＬＢミスを減らすことにつながる。
【００１９】
しかし、このようにデータ割当て方式がサイクリック割当て方式であったとしても、依然としてＴＬＢスラッシングが発生する可能性がある。その理由は次のとおりである。
すなわち、同時実行されるスレッド数が多いプロセッサにおいて採用されるプログラムの実行モデルは、多くの場合、スレッド間の同期をとる必要のないＳＰＭＤ（Single Program Multiple Data）である。なぜならば、ＳＰＭＤは、スレッド間の同期をとる必要のあるＳＩＭＤ（Single Instruction Multiple Data）と比較すると、実行準備の整ったスレッドから順次実行することができるため、一般的には、プロセッサの空き時間が少なくなり、実行性能が高いからである。
【００２０】
しかし、ＳＰＭＤは、このように同期をとる必要がない分だけ、スレッド間に進行速度の差が発生する。そして、スレッド間の進行速度の差が大きくなると、サイクリック割当て方式を採用した場合においても、各スレッドによるアクセス領域が分散してしまうこととなる。進行速度の速いスレッドは、他のスレッドよりも早く、先のインデックスの配列を次々と処理するため、他のスレッドに先駆けて新しい記憶領域にアクセスするからである。
【００２１】
図２は、プログラムの実行モデルがＳＩＭＤの場合とＳＰＭＤの場合とにおける、各スレッド（スレッド０〜スレッド３）によりアクセスされる記憶領域の分散状況について、スレッドの進行速度の差との関係が明確になるように示した図である。図２に示すように、スレッド間の進行速度に差が生じにくいＳＩＭＤでは、各スレッドによるアクセス領域が局所に集中する一方、スレッド間の進行速度に差が生じやすいＳＰＭＤでは、各スレッドによるアクセス領域が分散する。その結果、ＳＰＭＤでは、同時にアクセス対象となるページ数が多くなり、ＴＬＢミスが頻発し、ＴＬＢスラッシングが発生してしまう。
【００２２】
また、図３は、ＳＰＭＤの実行モデルにおいて、ある記憶領域のデータを別の記憶領域にコピーするプログラムを実行した場合における、メモリバンド幅の測定結果を示す。縦軸は、プログラム実行時に測定されたメモリバンド幅を示す。横軸は、コピー処理において使用するバッファサイズを示す。かかるバッファサイズは、コピー処理においてアクセス対象となる記憶領域（コピー元及びコピー先を合わせた記憶領域）のサイズを示す。また、当該測定結果は、コピー処理において同時に用いるストリーム（配列）数（１ストリーム、４ストリーム、１６ストリーム及び６４ストリーム）に応じたメモリバンド幅を、理論値との対比において示したものである。
【００２３】
かかる図３の測定結果が示すように、アクセス対象となる記憶領域のサイズが十分に大きい場合、ストリーム数が多いほど、メモリバンド幅が減少する傾向にある。このようにアクセス対象となる記憶領域のサイズが十分に大きく、且つ、ストリーム数が多いときには、同時にアクセスされるページ数が多い。このような場合にメモリバンド幅が減少する傾向にあるということは、ＭＭＵにおいてＴＬＢミスが頻発し、ＴＬＢスラッシングが発生していることにより、処理効率が低下している可能性が高い。
【００２４】
そして、かかるＳＰＭＤの実行モデルにおいて、ＴＬＢスラッシングの発生を回避するためには、スレッド間の進行速度の差を縮めることが有効である。そうすることにより、各スレッドにより同時にアクセスされる記憶領域を局所に集中させることができ、同時にアクセス対象となるページ数を減少させることができるからである。かかるスレッド間の進行速度の差は、プログラム内に同期処理を追加する修正を施すことにより、ある程度縮めることが可能である。
【００２５】
図４は、前掲の図３に示したメモリバンド幅の測定条件において、プログラム内に同期処理を追加する修正を施した状態で測定し直した測定結果を示す。図４を図３と比較すると、アクセス対象となる記憶領域のサイズが十分に大きく、且つ、ストリーム数が多い場合であっても、メモリバンド幅の減少量が少なくなっていることがわかる。この測定結果は、スレッド間の進行速度の差が縮められたことにより、ＴＬＢスラッシングの発生が抑制されたことを示している。
【００２６】
しかし、プログラム開発者がプログラムに適切な同期処理を追加する修正を施すには、プロセッサアーキテクチャの理解が不可欠であり、かかる修正は高度な知識を必要とする。このため、プログラム修正を施す必要のない方法によって、スレッド間の進行速度の差を抑えるほうが、さらに望ましい。
【００２７】
そこで、以下、スレッド間の進行速度の差を縮めることが可能な記憶管理機構について説明する。
本記憶管理機構は、進行速度の速いスレッドが他のスレッドに先駆けて新しい記憶領域にアクセスする傾向が強いという特徴を利用して、スレッド間の進行速度の差を縮めるものである。具体的には、本記憶管理機構は、プログラムの実行中にＴＬＢミスが発生した場合であって、そのＴＬＢミスに係る論理アドレスが、実行中のプログラムにおいて未だアクセスしたことのない新規なアドレスであったときに、ＴＬＢミスの解決処理を遅延させる。その結果、本記憶管理機構は、進行速度の速いスレッドの進行を遅延させることができ、スレッド間の進行速度の差を調整することができる。
【００２８】
図５は、本記憶管理機構を含んだ計算機システムの一実施例のブロック図である。本計算機システムは、プロセッサ１０及びメモリ１１を含む。プロセッサ１０及びメモリ１１は、外部バスで相互に接続されている。
【００２９】
プロセッサ１０は、実行ユニット１２、ＭＭＵ１３、及びメモリインタフェース１４を含む。プロセッサ１０内において、実行ユニット１２、ＭＭＵ１３及びメモリインタフェース１４は、内部バスで相互に接続されている。
【００３０】
実行ユニット１２は、メモリ１１に格納されたプログラムの命令を実行する装置であり、制御ユニット（Control Unit）、演算ユニット（Arithmetic Logic Unit）及び命令デコーダ等を含む。そして、実行ユニット１２は、命令デコーダで解読されたプログラムの命令に従い、制御ユニットより出力される制御信号に応じ、演算ユニットを用いて算術・論理演算を実行する。このとき、実行ユニット１２は、実行中のプログラムにおいて、メモリ１１へのアクセス要求が発生したときに、そのアクセス対象となる論理アドレスが含まれるページの論理アドレス（以下、「対象論理アドレス」という）を、ＭＭＵ１３に対して送信する。また、実行ユニット１２は、ＭＭＵ１３から、対象論理アドレスに対応する物理アドレスを受信し、当該物理アドレス及びページ内オフセットを用い、メモリインタフェース１４を介してメモリ１１にアクセスする。
【００３１】
ＭＭＵ１３は、メモリ１１の記憶領域をページ分割して管理する。また、ＭＭＵ１３は、仮想記憶における論理アドレスから物理アドレスへの変換を行う。そして、ＭＭＵ１３は、ＭＭＵ制御部１５、ＴＬＢ１６、ＥＡＢ（Evicted Address Buffer）１７及び遅延バッファ１８を含む。
【００３２】
ＭＭＵ制御部１５は、例えば、マイクロプログラム制御機構、又は、論理回路の組合せである。そして、ＭＭＵ制御部１５は、ＴＬＢ１６を用いて、実行ユニット１２から受信した対象論理アドレスを物理アドレスに変換し、実行ユニット１２に物理アドレスを返信する。
【００３３】
ＴＬＢ１６は、論理アドレス及び当該論理アドレスに対応する物理アドレスを関連付けるエントリを含むバッファである。そして、ＴＬＢ１６のエントリの構造は、論理アドレス（図５ではＶＡ（Virtual Address）と略記されている）及び物理アドレス（図５ではＰＡ（Physical Address）と略記されている）を含む。ＴＬＢ１６は、ＭＭＵ１３の内部に設置され、後述するページテーブル２５のキャッシュとしての機能を果たす。このため、ＭＭＵ制御部１５は、ＴＬＢ１６を用いることで、論理アドレスから物理アドレスへの変換を高速に行うことができる。ここで、ＴＬＢ１６のエントリ数には上限がある。このため、ＴＬＢ１６は、プログラムの実行において最後にアクセス対象となったページの論理アドレスから、最大でＴＬＢ１６のエントリの上限数だけ前にアクセス対象となったページの論理アドレスまでの、各論理アドレスに対応するエントリを含む。なお、ＴＬＢ１６が、第１テーブルに相当する。
【００３４】
ＥＡＢ１７は、論理アドレスを蓄積可能なバッファであり、アクセス対象となったことがあるページの論理アドレスが蓄積される。つまり、ＥＡＢ１７は、ＴＬＢから追い出されたページエントリのアドレスを蓄積しておくバッファである。なお、ＥＡＢ１７が、第２テーブルに相当する。
【００３５】
遅延バッファ１８は、後述するページテーブル２５からエントリを読み出すための要求に係るデータが一時的に退避されるバッファである。
メモリ１１は、記憶装置であり、例えば、主記憶装置やキャッシュメモリ等である。また、メモリ１１は、実行対象のプログラムの命令データや処理対象データを含む一方、論理アドレスと物理アドレスとを関連付けるエントリを含んだページテーブル２５を含む。図５の例では、ページテーブル２５のエントリの構造は、物理アドレスを含んでいる。そして、各エントリは、当該物理アドレスの配置自体が論理アドレスを示すことで、論理アドレス及び物理アドレスを関連付けている。ここで、ページテーブル２５とプログラムの命令データや処理対象データとは必ずしも同一の装置内に存在する必要はなく、例えば、ページテーブル２５がキャッシュメモリに存在し、プログラムの処理対象データが主記憶装置に存在してもよい。
【００３６】
次に、ＭＭＵ制御部１５の構成要素及び機能についてさらに詳述する。ＭＭＵ制御部１５は、アドレス変換部１９、ＴＬＢ比較部２０、ＥＡＢ比較部２１、遅延制御部２２、ページテーブル読出部２３及び登録部２４を含む。また、図６は、ＭＭＵ制御部１５で行われる動作を示すフローチャートである。以下、図５及び図６を参照し、ＭＭＵ制御部１５の各構成要素の動作について説明する。以下に示すステップ１〜ステップ９は、夫々、図６に示すＳ１〜Ｓ９に対応する。なお、ＴＬＢ比較部２０が、第１判定部又は第１判定手順として機能する。また、ＥＡＢ比較部２１が、第２判定部として機能する。さらに、遅延制御部２２が、遅延制御部又は遅延制御手順として機能する。
【００３７】
まず、アドレス変換部１９が、実行ユニット１２から、対象論理アドレスを受信する（ステップ１）。ＴＬＢ比較部２０が、対象論理アドレスとＴＬＢに含まれるエントリの論理アドレスとを比較し、対象論理アドレスに対応するエントリがＴＬＢ１６に存在するか否かを判定する（ステップ２）。ここで、対象論理アドレスに対応するエントリがＴＬＢ１６に存在する場合（ＴＬＢヒットの場合）には（Ｙｅｓ）、後述のステップ９の動作に移る。一方、対象論理アドレスに対応するエントリがＴＬＢ１６に存在しない場合（ＴＬＢミスの場合）には（Ｎｏ）、ＥＡＢ比較部２１が、対象論理アドレスとＥＡＢ１７に含まれるエントリの論理アドレスとを比較し、対象論理アドレスがＥＡＢ１７に存在するか否かを判定する（ステップ３）。ここで、対象論理アドレスがＥＡＢ１７に存在する場合（ＥＡＢヒットの場合）には（Ｙｅｓ）、後述のステップ５の動作に移る。一方、対象論理アドレスがＥＡＢ１７に存在しない場合（ＥＡＢミスの場合）には（Ｎｏ）、遅延制御部２２が、ページテーブル読出部２３の動作を制御する。具体的には、遅延制御部２２が、ページテーブル読出部２３が送信する、ページテーブル２５のエントリを読み出すための要求に係るデータを、遅延バッファ１８に所定時間退避させる。すなわち、遅延制御部２２は、所定時間経過するまで、ページテーブル２５のエントリの読み出しを遅延させる（ステップ４）。なお、遅延させる所定時間は、例えば、クロック数等などにより予め遅延制御部２２において設定された時間である。
【００３８】
そして、ページテーブル読出部２３は、メモリインタフェース１４に対して、ページテーブル２５に格納されている対象論理アドレスに対応するエントリを読み出すための要求に係るデータを送信する（ステップ５）。ページテーブル読出部２３は、メモリインタフェース１４から、ページテーブル２５に格納されている対象論理アドレスに対応するエントリを読み出す（ステップ６）。登録部２４は、対象論理アドレスと、ページテーブル２５から読み出したエントリが示す物理アドレスと、を関連付ける新規エントリをＴＬＢ１６に登録する（ステップ７）。ここで、このステップ７において、ＴＬＢ１６のエントリ数が既に上限数に達していた場合には、登録部２４は、ＴＬＢ１６に最古に登録されていた最古エントリの代わりに、新規エントリを登録する。この場合には、登録部２４は、ＴＬＢ１６の最古エントリ、すなわちＴＬＢ１６から追い出されるエントリの論理アドレスを、ＥＡＢ１７に登録する（ステップ８）。
【００３９】
そして、アドレス変換部１９は、ＴＬＢ１６のエントリに基づいて、対象論理アドレスを、当該対象論理アドレスに対応する物理アドレスに変換する。すなわち、アドレス変換部１９は、ＴＬＢ１６のエントリのうち、対象論理アドレスに対応するエントリが示す物理アドレスを、実行ユニット１２に送信する（ステップ９）。
【００４０】
以上のような各構成要素によれば、本記憶管理機構は、対象論理アドレスを物理アドレスに変換するときに、次のような動作を行う。すなわち、本記憶管理機構は、ＴＬＢミスが発生したときに、対象論理アドレスがプログラムの実行中において未だアクセス対象となっていないページの論理アドレスであるときには、アドレス変換のタイミングを遅延させる。これにより、プログラムの実行中において未だアクセス対象となっていないページの論理アドレスにアクセスするスレッド、すなわち進行速度の速いスレッドにおけるアドレス変換が遅延され、進行速度の速いスレッドの進行が遅延される。このため、各スレッド間の進行速度が調整される。
【００４１】
具体的には、本記憶管理機構は、ＴＬＢミスが発生したときに、その解決処理として、次の動作を行う。すなわち、本記憶管理機構は、対象論理アドレスに対応する新規エントリをＴＬＢ１６に登録するとともに、ＴＬＢ１６から追い出された論理アドレスを、ＥＡＢ１７に登録する。これにより、ＴＬＢミスが発生した論理アドレスであって、プログラムの実行中に既にアクセス対象となったページの論理アドレスは、少なくともＴＬＢ１６又はＥＡＢ１７のいずれかに含まれることとなる。換言すれば、ＴＬＢミスが発生した論理アドレスであって、ＥＡＢ１７にも存在しない論理アドレスは、プログラムの実行中において未だアクセスされていないページの論理アドレスである可能性が高いということになる。
【００４２】
そして、本記憶管理機構は、実行ユニット１２から対象論理アドレスを受信したときに、当該論理アドレスが、ＴＬＢミスが発生した論理アドレスであって、且つ、ＥＡＢ１７にも存在しない論理アドレスであるか否かを判定する。換言すれば、本記憶管理機構は、対象論理アドレスが、プログラムの実行中に未だアクセス対象となっていないページの論理アドレスであるか否かを判定する。そして、本記憶管理機構は、対象論理アドレスが、プログラムの実行中に未だアクセス対象となっていないページの論理アドレスである可能性が高いときには、ページテーブル２５に格納されたエントリの読み出しの要求に係るデータの送信を所定時間遅延させる。これにより、ＴＬＢ１６に当該論理アドレスに対応するエントリが登録されるタイミングが遅延する。その結果、実行ユニット１２に物理アドレスが返信されるタイミングが遅延し、実行ユニット１２がメモリ１１にアクセスできるタイミングが遅延する。このため、進行速度の早いスレッドの進行が遅延し、スレッド間の進行速度が調整されることとなる。したがって、本記憶管理機構は、プログラム内に同期処理を追加する修正を施した場合と同様に、スレッド間の進行速度の差を縮めることできる。
【００４３】
さらに、このようにスレッド間の進行速度の差が縮められる結果、プログラムの実行中に、各スレッドにより同時にアクセスされる記憶領域が局所に集中する傾向が強くなる。このため、プログラムの各スレッドが同時にアクセスするページ数が減少し、ＴＬＢミスの発生頻度が減少する。その結果、ＴＬＢスラッシングの発生が抑制され、論理アドレスから物理アドレスへのアドレス変換が高速に行われ、プログラムの実行時間が短縮されることとなる。
【００４４】
なお、本記憶管理機構では、ＥＡＢ１７を用いることにより、対象論理アドレスが既にアクセス対象となった論理アドレスであるか否かの判定を実現させている。しかし、本記憶管理機構は、対象論理アドレスが既にアクセス対象となった論理アドレスであるか否かを判定することができる方法であれば、ＥＡＢ１７を用いる方法に限らず、いかなる方法を用いることもできる。
【００４５】
また、本記憶管理機構では、遅延制御部２２が、遅延バッファ１８を用いてページテーブル２５からエントリを読み出すタイミングを遅延させることにより、論理アドレスから物理アドレスへのアドレス変換を遅延させている。しかし、アドレス変換を遅延させる方法は、かかる方法に限らない。例えば、遅延制御部２２は、遅延バッファ１８を用いる方法以外の方法で遅延制御を行ってもよい。また、遅延制御部２２は、ページテーブル２５のエントリを読み出した後で、ＴＬＢ１６への新規エントリを登録する動作を遅延させてもよい。このようにしても、結果として、対象論理アドレスを物理アドレスに変換するタイミングが遅延することに変わりはなく、進行速度の速いスレッドの進行を遅延させることができる。
【００４６】
さらに、本記憶管理機構では、登録部２４が、ＥＡＢ１７に対し、ＴＬＢ１６から追い出されたエントリの論理アドレスを登録している。しかし、例えば、登録部２４は、実行ユニット１２から受信した対象論理アドレス全てをＥＡＢ１７に登録するようにしてもよい。また、登録部２４は、重複する論理アドレスをＥＡＢ１７に登録しないように制御してもよい。このようにしても、本記憶管理機構は、対象論理アドレスが前記プログラムの実行中にアクセス対象となったことがあるか否かを判定することができる。
【符号の説明】
【００４７】
１０  プロセッサ
１１  メモリ
１２  実行ユニット
１３  ＭＭＵ
１４  メモリインタフェース
１５  ＭＭＵ制御部
１６  ＴＬＢ
１７  ＥＡＢ
１８  遅延バッファ
１９  アドレス変換部
２０  ＴＬＢ比較部
２１  ＥＡＢ比較部
２２  遅延制御部
２３  ページテーブル読出部
２４  登録部
２５  ページテーブル
【図１】
0005428617.tif 000003
【図２】
0005428617.tif 000004
【図３】
0005428617.tif 000005
【図４】
0005428617.tif 000006
【図５】
0005428617.tif 000007
【図６】
0005428617.tif 000008