(57)【要約】【課題】ハイブリッド・アドレス変換のためのコンピュータ・プログラム、システム、および方法を提供する。【解決手段】本発明の実施形態はハイブリッド・アドレス変換に関する。本発明の態様は、第１のアドレス空間における位置を参照する第１のアドレスを受信することを含む。コンピュータは、セグメント・ルックアサイド・バッファ（ＳＬＢ）において、第１のアドレスに対応するＳＬＢエントリを検索する。ＳＬＢエントリは、タイプ・フィールドおよびアドレス・フィールドを含む。更にコンピュータは、ＳＬＢエントリにおけるタイプ・フィールドの値がハッシュ・ページ・テーブル（ＨＰＴ）検索または基数木検索のどちらを示すかを判定する。タイプ・フィールドの値がＨＰＴ検索を示すという判定に基づいて、ＨＰＴを検索して第２のアドレスを決定する。第２のアドレスは、第１のアドレスの第２のアドレス空間への変換を含む。タイプ・フィールドの値が基数木検索を示すという判定に基づいて、基数木を検索して第２のアドレスを決定する。【選択図】図３
2015515057.tif 000002
【特許請求の範囲】
【請求項１】
ハイブリッド・アドレス変換を実施するためのコンピュータ・プログラムであって、
処理回路によって読み取り可能であり、方法を実行するために前記処理回路によって実行される命令を記憶している有形の記憶媒体を含み、前記方法が、
第１のアドレス空間における位置を参照する第１のアドレスを受信することと、
セグメント・ルックアサイド・バッファ（ＳＬＢ）において、前記第１のアドレスに対応するＳＬＢエントリを検索することであって、前記ＳＬＢエントリがタイプ・フィールドおよびアドレス・フィールドを含む、ことと、
前記ＳＬＢエントリにおける前記タイプ・フィールドの値がハッシュ・ページ・テーブル（ＨＰＴ）検索または基数木検索のどちらを示すかを判定することと、
前記タイプ・フィールドの前記値が前記ＨＰＴ検索を示すという判定に基づいて、ＨＰＴを検索して第２のアドレスを決定することであって、前記第２のアドレスが前記第１のアドレスの第２のアドレス空間への変換を含む、ことと、
前記タイプ・フィールドの前記値が前記基数木検索を示すという判定に基づいて、基数木を検索して前記第２のアドレスを決定することと、
を含む、コンピュータ・プログラム。
【請求項２】
前記ＨＰＴを検索して前記第２のアドレスを決定することが、
前記第１のアドレスに対応する前記ＳＬＢエントリの前記アドレス・フィールドから前記第１のアドレスに関連付けられた仮想アドレスを抽出することと、
前記ＨＰＴにおいて前記仮想アドレスを検索することと、
を含む、請求項１に記載のコンピュータ・プログラム。
【請求項３】
前記基数木を検索して前記第１のアドレスに関連付けられた前記第２のアドレスを決定することが、
前記第１のアドレスに対応する前記ＳＬＢエントリの前記アドレス・フィールドから前記第１のアドレスに関連付けられたアドレス空間識別子（ＩＤ）およびセグメント・サイズを抽出することと、
前記アドレス空間ＩＤおよび前記セグメント・サイズに基づいて前記基数木検索のルートを決定することと、
前記基数木において前記ルートから開始して前記第１のアドレスを検索することと、
を含む、請求項１に記載のコンピュータ・プログラム。
【請求項４】
前記アドレス空間ＩＤが前記第１のアドレスに関連付けられたプロセスＩＤを含む、請求項３に記載のコンピュータ・プログラム。
【請求項５】
前記アドレス空間ＩＤおよび前記セグメント・サイズは、前記ルートが前記基数木のトップ・レベルよりも下の前記基数木のレベルであることを示し、前記基数木における前記第１のアドレスの前記検索が前記基数木の前記トップ・レベルよりも下の前記レベルで開始することによって前記基数木の前記トップ・レベルは検索しないようになっている、請求項３に記載のコンピュータ・プログラム。
【請求項６】
前記第１のアドレスが、メモリ・アクセスの一部としてコンピュータ上で動作しているアプリケーションにより発行された有効アドレスを含み、前記第２のアドレスが実アドレスを含み、前記第２のアドレス空間が前記コンピュータの物理コンピュータ・メモリを含む、請求項１に記載のコンピュータ・プログラム。
【請求項７】
前記タイプ・フィールドの前記値が、前記第１のアドレスに関連付けられたメモリ・アクセスのタイプおよびアプリケーションのタイプの少なくとも一方に基づく、請求項１に記載のコンピュータ・プログラム。
【請求項８】
前記第１のアドレス空間が複数の不連続メモリ領域を含む、請求項１に記載のコンピュータ・プログラム。
【請求項９】
ハイブリッド・アドレス変換のためのコンピュータ・システムであって、
アドレス変換論理と、
セグメント・ルックアサイド・バッファ（ＳＬＢ）と、を含み、前記システムが、
前記アドレス変換論理によって、第１のアドレス空間における位置を参照する第１のアドレスを受信することと、
前記アドレス変換論理によって、前記ＳＬＢにおいて、前記第１のアドレスに対応するＳＬＢエントリを検索することであって、前記ＳＬＢエントリがタイプ・フィールドおよびアドレス・フィールドを含む、ことと、
前記ＳＬＢエントリにおける前記タイプ・フィールドの値がハッシュ・ページ・テーブル（ＨＰＴ）検索または基数木検索のどちらを示すかを判定することと、
前記タイプ・フィールドの前記値が前記ＨＰＴ検索を示すという判定に基づいて、ＨＰＴを検索して第２のアドレスを決定することであって、前記第２のアドレスが前記第１のアドレスの第２のアドレス空間への変換を含む、ことと、
前記タイプ・フィールドの前記値が前記基数木検索を示すという判定に基づいて、基数木を検索して前記第２のアドレスを決定することと、
を含む方法を実行するように構成されている、システム。
【請求項１０】
前記ＨＰＴを検索して前記第２のアドレスを決定することが、
前記第１のアドレスに対応する前記ＳＬＢエントリの前記アドレス・フィールドから前記第１のアドレスに関連付けられた仮想アドレスを抽出することと、
前記ＨＰＴにおいて前記仮想アドレスを検索することと、
を含む、請求項９に記載のコンピュータ・システム。
【請求項１１】
前記基数木を検索して前記第１のアドレスに関連付けられた前記第２のアドレスを決定することが、
前記第１のアドレスに対応する前記ＳＬＢエントリの前記アドレス・フィールドから前記第１のアドレスに関連付けられたアドレス空間識別子（ＩＤ）およびセグメント・サイズを抽出することと、
前記アドレス空間ＩＤおよび前記セグメント・サイズに基づいて前記基数木検索のルートを決定することと、
前記基数木において前記ルートから開始して前記第１のアドレスを検索することと、
を含む、請求項９に記載のコンピュータ・システム。
【請求項１２】
前記アドレス空間ＩＤが前記第１のアドレスに関連付けられたプロセスＩＤを含む、請求項１１に記載のコンピュータ・システム。
【請求項１３】
前記アドレス空間ＩＤおよび前記セグメント・サイズは、前記ルートが前記基数木のトップ・レベルよりも下の前記基数木のレベルであることを示し、前記基数木における前記第１のアドレスの前記検索が前記基数木の前記トップ・レベルよりも下の前記レベルで開始することによって前記基数木の前記トップ・レベルは検索しないようになっている、請求項１１に記載のコンピュータ・システム。
【請求項１４】
前記第１のアドレスが、メモリ・アクセスの一部としてコンピュータ上で動作しているアプリケーションにより発行された有効アドレスを含み、前記第２のアドレスが実アドレスを含み、前記第２のアドレス空間が前記コンピュータの物理コンピュータ・メモリを含む、請求項９に記載のコンピュータ・システム。
【請求項１５】
前記タイプ・フィールドの前記値が、前記第１のアドレスに関連付けられたメモリ・アクセスのタイプおよびアプリケーションのタイプの少なくとも一方に基づく、請求項９に記載のコンピュータ・システム。
【請求項１６】
コンピュータにおけるハイブリッド・アドレス変換のためのコンピュータ実施方法であって、
第１のアドレス空間における位置を参照する第１のアドレスを受信することと、
前記コンピュータによって、セグメント・ルックアサイド・バッファ（ＳＬＢ）において、前記第１のアドレスに対応するＳＬＢエントリを検索することであって、前記ＳＬＢエントリがタイプ・フィールドおよびアドレス・フィールドを含む、ことと、
前記ＳＬＢエントリにおける前記タイプ・フィールドの値がハッシュ・ページ・テーブル（ＨＰＴ）検索または基数木検索のどちらを示すかを判定することと、
前記タイプ・フィールドの前記値が前記ＨＰＴ検索を示すという判定に基づいて、ＨＰＴを検索して第２のアドレスを決定することであって、前記第２のアドレスが前記第１のアドレスの第２のアドレス空間への変換を含む、ことと、
前記タイプ・フィールドの前記値が前記基数木検索を示すという判定に基づいて、基数木を検索して前記第２のアドレスを決定することと、
を含む、コンピュータ実施方法。
【請求項１７】
前記ＨＰＴを検索して前記第２のアドレスを決定することが、
前記第１のアドレスに対応する前記ＳＬＢエントリの前記アドレス・フィールドから前記第１のアドレスに関連付けられた仮想アドレスを抽出することと、
前記ＨＰＴにおいて前記仮想アドレスを検索することと、
を含む、請求項１６に記載のコンピュータ実施方法。
【請求項１８】
前記基数木を検索して前記第１のアドレスに関連付けられた前記第２のアドレスを決定することが、
前記第１のアドレスに対応する前記ＳＬＢエントリの前記アドレス・フィールドから前記第１のアドレスに関連付けられたアドレス空間識別子（ＩＤ）およびセグメント・サイズを抽出することと、
前記アドレス空間ＩＤおよび前記セグメント・サイズに基づいて前記基数木検索のルートを決定することと、
前記基数木において前記ルートから開始して前記第１のアドレスを検索することと、
を含む、請求項１６に記載のコンピュータ実施方法。
【請求項１９】
前記アドレス空間ＩＤが前記第１のアドレスに関連付けられたプロセスＩＤを含む、請求項１８に記載のコンピュータ実施方法。
【請求項２０】
前記アドレス空間ＩＤおよび前記セグメント・サイズは、前記ルートが前記基数木のトップ・レベルよりも下の前記基数木のレベルであることを示し、前記基数木における前記第１のアドレスの前記検索が前記基数木の前記トップ・レベルよりも下の前記レベルで開始することによって前記基数木の前記トップ・レベルは検索しないようになっている、請求項１８に記載のコンピュータ実施方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般にコンピューティング・システムに関し、更に特定すればコンピュータ・アドレッシング技法に関する。
【背景技術】
【０００２】
今日のコンピュータ・システムにおいて、システム・メモリはオペレーティング・システムによって管理され、必要に応じて異なるソフトウェア・アプリケーションに割り当てられる。異なるソフトウェア・アプリケーションは１つ以上のパーティションにおいて動作する場合があり、１つ以上のパーティションは異なるオペレーティング・システム（ＯＳ）を実行することがある。かかるコンピュータ・システムでは、仮想メモリ技法を用いて、多くのプロセスおよびアプリケーションの間でコンピューティング・システムの物理メモリを共有することができる。従って、ソフトウェア・アプリケーションは仮想メモリ空間において有効アドレスを処理し、これによってアプリケーションは必要な場合に読み取り、書き込み、および実行を行うことができ、しかもこれらの動作が行われている実際の物理メモリ位置に関与することはない。アプリケーションは、各アプリケーションの基礎にあるオペレーティング・システムに頼って、アプリケーションが用いる有効アドレスからコンピュータ・メモリ内の物理アドレスへのマッピングを実行する。アドレス変換は、仮想メモリを参照する有効アドレスが実メモリ・アドレスに変換されるメカニズムである。アドレス変換は複雑な手順であり、適切に実施されない場合には、プロセッサのクロック・サイクルを決定するクリティカル・パスになりかねない。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
ＣＰＵが有効アドレスを要求した場合、システムは最初に有効アドレス−実アドレス変換（ＥＲＡＴ：effective-to-real address translation）キャッシュをチェックして、その有効アドレスに対応した実アドレスを確定する。ＥＲＡＴキャッシュ内に有効アドレスが存在しない場合、セグメント・ルックアサイド・バッファ（ＳＬＢ：segment lookaside buffer）および変換ルックアサイド・バッファ（ＴＬＢ：translation lookaside buffer）を含む様々な他のキャッシュをチェックして、有効アドレスに対応した実アドレスを確定することができる。ＥＲＡＴキャッシュ、ＳＬＢ、およびＴＬＢは、最近用いた有効アドレスの変換に関するデータを保持し、アドレス変換プロセスに必要な情報を提供するために検索される。しかしながら、これらのキャッシュのいずれにも有効アドレスが存在しない場合は、有効アドレスの正しい変換を決定するために、追加のページ・テーブル検索を実行しなければならない。
【課題を解決するための手段】
【０００４】
実施形態は、ハイブリッド・アドレス変換のためのコンピュータ・プログラム、システム、および方法を含む。本発明の態様は、第１のアドレス空間における位置を参照する第１のアドレスを受信することを含む。コンピュータは、セグメント・ルックアサイド・バッファ（ＳＬＢ）において、第１のアドレスに対応するＳＬＢエントリを検索する。ＳＬＢエントリは、タイプ・フィールドおよびアドレス・フィールドを含む。更にコンピュータは、ＳＬＢエントリにおけるタイプ・フィールドの値がハッシュ・ページ・テーブル（ＨＰＴ）検索または基数木検索のどちらを示すかを判定する。タイプ・フィールドの値がＨＰＴ検索を示すという判定に基づいて、ＨＰＴを検索して第２のアドレスを確定する。第２のアドレスは、第１のアドレスの第２のアドレス空間への変換を含む。タイプ・フィールドの値が基数木検索を示すという判定に基づいて、基数木を検索して第２のアドレスを確定する。
【０００５】
本発明の教示を通して、更に別の特性および利点が実現される。本発明の他の実施形態および態様は、本明細書において詳細に説明され、特許請求される本発明の一部と見なされる。本発明をその利点および特性と共により良く理解するため、以下の記載および図面を参照する。
【０００６】
本発明と見なされる主題は、本明細書の最後の特許請求の範囲において具体的に指摘され、明確に特許請求される。本発明の前述および他の特性および利点は、添付図面と関連付けて以下の詳細な説明を読むことによって明らかとなる。
【図面の簡単な説明】
【０００７】
【図１】一実施形態に従ったハイブリッド・アドレス変換のためのシステムを示す。
【図２】一実施形態に従ったハイブリッド・アドレス変換のためのシステムを示す。
【図３】一実施形態に従ったハイブリッド・アドレス変換のための方法のプロセス・フローを示す。
【図４】一実施形態に従った基数木を検索するための方法のプロセス・フローを示す。
【図５】一実施形態に従った基数木を検索するための方法のプロセス・フローを示す。
【図６】一実施形態に従った基数木を検索するための方法のプロセス・フローを示す。
【図７】一実施形態に従ったハッシュ・ページ・テーブルを検索するための方法のプロセス・フローを示す。
【図８】一実施形態に従ったコンピュータ・プログラムを示す。
【発明を実施するための形態】
【０００８】
ハイブリッド・アドレス変換のためのシステムおよび方法の実施形態を提供し、例示的な実施形態について以下で詳細に論じる。ハイブリッド・アドレス変換では、異なるタイプのページ・テーブル、特にハッシュ・ページ・テーブル（ＨＰＴ：hashed page table）および基数木を、単一のコンピューティング・システムにおいて用いて、第１のアドレスの第２のアドレスへの変換を実現することができる。特定のアドレス変換に用いられるページ・テーブルのタイプは、要求のタイプまたは変換対象のアドレスを発行したアプリケーションの基礎にあるＯＳあるいはその両方に基づく。ＨＰＴは、比較的大きいデータセットにおける少ないランダムなアクセスに好適であり、基数木は、空間的局所性の高いアクセスに好適である。従って、例えば、データベースＤＢ２等のメモリ設置面積の大きいアプリケーションにおけるデータ側アクセスはＨＰＴに向いている場合があるが、命令側アクセスは基数木を用いることがある。ハイブリッド・アドレス変換スキームでは、単一のコンピューティング・システム上で動作している異なるソフトウェア・アプリケーションについて、それらのソフトウェア・アプリケーションまたはメモリ・アクセスのそれぞれのタイプに適した特定のタイプのアドレス変換を用いることによって性能を向上させることができる。更に、アドレス変換は、多数の不連続メモリ領域を横断して実行することも可能であり、基数木の検索では多数の基数木のルート（root）を使用して基数木変換の実行に必要な時間量を軽減することができる。
【０００９】
特定のアドレス変換に用いるページ・テーブル検索タイプを決定するために、各アドレスのＳＬＢエントリは、その特定のアドレスに対してＨＰＴまたは基数木検索のどちらを用いるべきであるかを示すそれぞれのタイプ・フィールドを含む。タイプ・フィールドは単一のビットを含み、ＳＬＢエントリ内のいずれかの適切な位置に含ませることができる。基数木またはＨＰＴの検索を示すために、いずれかの適切なタイプ値を用いることができる。以下の考察では、タイプ値０はＨＰＴ検索を示し、タイプ値１は基数木検索を示す。しかしながら、これは単に例示の目的のためのものである。
【００１０】
また、ＳＬＢエントリは、基数木検索のルートを決定するために用いる基数木ポインタも含むことができる。基数木検索ルート・ポインタとしてＳＬＢ仮想空間識別子（ＶＳＩＤ：virtual space identifier）を利用することができる。基数木ポインタは、アドレスが検索される基数木におけるエントリ・ブロックを示すアドレス空間識別子（ＩＤ）を含むことができる。エントリ・ブロックのサイズは、検索対象の基数木のレベル数を決定する。すなわち、エントリ・ブロックのサイズが大きいと、基数木におけるレベルが高い。基数木内の有効葉エントリは、木におけるレベルに対応したページ・サイズを示す。アドレスに関連付けられたアドレス空間ＩＤは、有効アドレスをその固有サイズよりも拡張するいずれかの機構を用いてＳＬＢエントリに記憶することができる。かかるアドレス拡張は、ソフトウェア要求に応じてゼロ・ビットまで小さくすることができる。アドレス空間ＩＤはプロセス識別子（ＰＩＤ）を含むことができ、これは、いくつかの実施形態ではアドレスに関連付けられた外部ＰＩＤである場合がある。基数木有効アドレスは４８ビットに指定されているので、上位１６ビットがゼロ以外の値にセットされた有効アドレスは暗黙的なアドレス空間ＩＤと見ることができる。基数木検索ルートを示すためにＳＬＢエントリ内のアドレス空間ＩＤを用いることによって、完全アドレス空間をカバーする基数木を提供することなく、多数の不連続メモリ領域を横断した検索が可能となる。有効アドレスの更に多くの上位ビットが一致する場合、木のウォーク（walk）は、ページ・テーブル・ルート・ポインタを用いる完全指定基数木よりも短い距離（例えば４ステップ未満）とすることができる。例えばソフトウェアは、頻繁に行われる変換については明示的にもっと多くのビットを指定することができ、またはハードウェアは、ＳＬＢエントリのいくつかをページ・ウォーク・キャッシュとして管理することができ、最大数の一致上位ビットを含むＳＬＢを選択するための貪欲アルゴリズムを用いる。ウォークを行うレベル数を減らすために、ＳＬＢエントリに一致する最小セグメント・サイズを用いて基数木ウォークを開始する。また、アドレス空間ＩＤは、例えば異なるアドレス空間ＩＤに異なるコンテキストを割り当てることによって、不必要なＴＬＢのフラッシュを防ぐことができる。
【００１１】
以下で図１から図２および図３から図７を参照して説明するハイブリッド・アドレス変換は、例えば入出力、パーティション・レベル、またはパーティション対物理レベル等、コンピューティング・システムにおけるいかなるタイプのアドレス変換にも用いることができる。図１から図２および図３から図７は、有効アドレスをコンピュータ・メモリ内の物理位置を示す実アドレスに変換することに関連付けて以下で論じるが、図３から図７に示す方法は、様々な実施形態におけるいかなるレベルのアドレス変換についても、第１のアドレス空間におけるいずれかのタイプの第１のアドレスを第２のアドレス空間におけるいずれかのタイプの第２のアドレスに変換するために使用可能である。
【００１２】
図１は、ハイブリッド・アドレス変換を含むコンピューティング・システム１００Ａの一例を示し、図２は、コンピューティング・システム１００Ａ等のコンピューティング・システムにおいて実施可能である、ＳＬＢエントリ、ＨＰＴ、および基数木を含むハイブリッド・アドレス変換のためのシステム１００Ｂの実施形態を示す。図１に示すコンピューティング・システム１００Ａは、プロセッサ１０１およびメイン・メモリ１０９を含む。プロセッサ１０１には、アドレス変換論理１０３、ＥＲＡＴキャッシュ１０４、ＳＬＢ１０５、およびＴＬＢ１０６が記憶されている。メイン・メモリ１０９には、複数のソフトウェア・アプリケーション１０２Ａ〜１０２Ｎ、ＨＰＴ１０７、および基数木１０８が記憶されている。ソフトウェア・アプリケーション１０２Ａ〜１０２Ｎの各々は、アドレス変換論理１０３を介してメイン・メモリ１０９内の特定の位置にアクセスする。有効アドレスはソフトウェア・アプリケーション１０２Ａ〜１０２Ｎによって発行され、アドレス変換論理１０３はこれらの有効アドレスを、メイン・メモリ１０９内の位置にアクセスするために使用可能である実アドレスに変換する。アドレス変換論理１０３は、アドレス変換を実行するために、ＨＰＴ１０７および基数木１０８の他に、ＥＲＡＴキャッシュ１０４、ＳＬＢ１０５、およびＴＬＢ１０５を含む様々なキャッシュを検索する。いくつかの実施形態において、ＥＲＡＴキャッシュ１０４は連想メモリ（ＣＡＭ：content addressable memory）を含むことができる。ＳＬＢ１０５は、各々が１つの有効アドレスに対応する複数のＳＬＢエントリを含む。ＴＬＢ１０６は、仮想アドレスに対応する複数の実アドレス変換を保持する。
【００１３】
図２に移ると、アドレス・フィールド１１１およびタイプ・フィールド１１１Ｂを含むＳＬＢエントリ１１０の一例が図示されている。ＳＬＢエントリ１１０は図１のＳＬＢ１０５に記憶することができる。タイプ・フィールド１１１Ｂは、ＳＬＢエントリ１１０内のアドレス・フィールド１１１Ａに記憶された有効アドレスを、ＨＰＴ１０７（例えばタイプ＝０）または基数木１０８（例えばタイプ＝１）のどちらで検索するべきかを示し、有効アドレスを発行したアプリケーションまたはメイン・メモリのタイプに基づくことができる。タイプ・フィールド１１１Ｂが０に等しく、ＨＰＴ１０７の検索を示すＳＬＢエントリでは、アドレス・フィールド１１１Ａは一致する有効アドレスに対応した仮想アドレスを含む。仮想アドレスはＴＬＢ１０６およびＨＰＴ１０７において検索される。タイプ・フィールド１１１Ｂが１に等しく、基数木１０８の検索を示すＳＬＢエントリでは、アドレス・フィールド１１１Ａは有効アドレスおよびアドレス空間ＩＤ情報を含み、これはＴＬＢ１０６および基数木１０８において検索される。アドレス・フィールド１１１Ａ内のアドレス空間ＩＤは、様々な実施形態において、ＰＩＤを含む場合があり、外部ＰＩＤである場合もある。基数木１０８は様々なレベルを含み、その各々がコンピューティング・システムにおけるメモリの異なるサイズのセグメントを表す。トップ・レベルの２５６テラバイト（ＴＢ）のセグメント１１２は、様々な５１２ギガバイト（ＧＢ）のサブ・セグメント１１３Ａ〜１１３Ｎを有する。５１２ＧＢのサブ・セグメント１１３Ａは、様々な１ＧＢのサブ・セグメント１１４Ａ〜１１４Ｎを有する。１ＧＢのサブ・セグメント１１４Ａは、２メガバイト（ＭＢ）のサブ・セグメント１１５を有する。タイプ１のＳＬＢエントリのアドレス・フィールド１１１Ａに含まれる有効アドレスおよびアドレス空間ＩＤ情報を用いて、基数木１０８の検索を開始するレベルを決定する。セグメント１１２、１１３Ａ〜１１３Ｎ、１１４Ａ〜１１４Ｎ、および１１５Ａは例示の目的のためにのみ示す。すなわち、基数木１０８等の基数木は、いずれかの適切な数、サイズ、および構造のセグメントおよびサブ・セグメントを含むことができる。
【００１４】
図３は、一実施形態に従ったハイブリッド・アドレス変換のための方法２００のプロセス・フローを示す。図３は、図１および図２を参照して論じ、アドレス変換論理１０３において実施可能である。最初にブロック２０１において、アプリケーション１０２Ａ〜１０２Ｎの１つが発行した変換対象の有効アドレスをＥＲＡＴキャッシュ１０４において検索する。次いでブロック２０２において、ＥＲＡＴキャッシュ１０４において有効アドレスが見つかったか否かを判定する。ＥＲＡＴキャッシュ１０４に有効アドレスが存在する場合、次いでブロック２０３において、ＥＲＡＴキャッシュ１０４からの変換を用いてメイン・メモリ１０９にアクセスし、方法２００のフローは終了する。しかしながら、ＥＲＡＴキャッシュ１０４に有効アドレスが存在しない場合は、次いでブロック２０４において、ＳＬＢ１０５でアドレスを検索し、ブロック２０５において、有効アドレスのＳＬＢエントリがＳＬＢ１０５に存在するか否かを判定する。ＳＬＢ１０５において有効アドレスのＳＬＢエントリ１１０が見つかった場合、次いで、その有効アドレスに関連付けられたタイプ・フィールド１１１Ｂが基数木検索またはＨＰＴ検索のどちらを示すか判定する。タイプ・フィールド１１１Ｂが基数木検索を示す場合、フローはブロック２０５からブロック２０６に進み、ＴＬＢ１０６および基数木１０８において、アドレス・フィールド１１１Ａが示す有効アドレスおよびこの有効アドレスに関連付けられたアドレス空間ＩＤを検索する。これについては図４から図６を参照して詳述する。有効アドレスのタイプ・フィールド１１１ＢがＨＰＴ検索を示す場合、フローはブロック２０５からブロック２０７に進み、ＴＬＢ１０６およびＨＰＴ１０７において、アドレス・フィールド１１１Ａが示す有効アドレスに関連付けられた仮想アドレスを検索する。これについては図７を参照して詳述する。ブロック２０５において、有効アドレスのＳＬＢエントリがＳＬＢ１０５に存在しない場合、ブロック２０８においてＳＬＢミス・フォルト（miss fault）を発行し、方法２００のフローは終了する。
【００１５】
図４は、一実施形態に従った基数木検索のための方法３００のプロセス・フローを示す。有効アドレスに関連付けられたＳＬＢエントリ１１０内のタイプ・フィールド１１１Ｂのタイプ・フィールドが基数木検索を示す場合、方法３００は、図３の方法２００のブロック２０６の間にアドレス変換論理１０３によって実行される。最初にブロック３０１において、ＳＬＢエントリ１１０内のアドレス・フィールド１１１Ａから、有効アドレスのアドレス空間ＩＤを抽出する。次いでブロック３０２では、ＴＬＢ１０６において、有効アドレスおよびこの有効アドレスに関連付けられたアドレス空間ＩＤを検索する。次いでブロック３０３において、有効アドレスおよびアドレス空間ＩＤがＴＬＢ１０６に存在するか否かを判定する。有効アドレスおよびアドレス空間ＩＤがＴＬＢ１０６内に存在する場合、ブロック３０４において、ＴＬＢ１０６において有効アドレスに与えられた実アドレス変換をＥＲＡＴキャッシュ１０４に挿入し、これを用いてメイン・メモリ１０９にアクセスする。しかしながら、ブロック３０３において有効アドレスおよびアドレス空間ＩＤがＴＬＢ内に存在しないと判定された場合、フローはブロック３０５に進み、基数木１０８において有効アドレスを検索し、アドレス空間ＩＤを用いて基数木検索のルートを決定する。
【００１６】
図５を参照して、方法３００のブロック３０５において実行される基数木１０８の検索について詳述する。これは、アドレス変換論理１０３によって実行され、一実施形態に従った、検索のルートとしてアドレス空間ＩＤを用いた有効アドレスの基数木検索のための方法４００のプロセス・フローを示す。最初にブロック４０１において、アドレス空間ＩＤに関連付けられたエントリ・ブロックのサイズを判定する。セグメント・サイズとも称されるエントリ・ブロックのサイズは、アドレス空間ＩＤによって示され、基数木１０８の検索を開始するレベルを表す。セグメント・サイズが大きいと、レベルが高く、基本木検索が有するステップが多いことが示されるが、セグメント・サイズが小さいと、レベルが低く、基本木検索が有するステップが少ないことが示される。図５に示すように、ブロック４０２Ａにおいて、２５６ＴＢのセグメント・サイズは４レベルの基数木検索を示す。ブロック４０２Ｂにおいて、５１２ＧＢのセグメント・サイズは３レベルの基数木検索を示す。ブロック４０２Ｃにおいて、１ＧＢのセグメント・サイズは２レベルの基数木検索を示す。ブロック４０２Ｄにおいて、２ＭＢのセグメント・サイズは１レベルの基数木検索を示す。しかしながら、図５に示すセグメント・サイズおよびレベル数は例示の目的のために示すだけであり、検索対象の基数木の構造に基づいて変動する場合がある。
【００１７】
基数木１０８において、ブロック４０２Ａ〜４０２Ｄで判定されたセグメント・サイズにより示されるレベルで開始して、有効アドレスを検索する。これについては図６を参照して詳述する。図６は、一実施形態に従った基数木検索のための方法５００のプロセス・フローを示す。方法５００が示す基数木検索は、図５のブロック４０１で判定したセグメント・サイズに応じて、ブロック５０１、５０４、５０７、または５１０のいずれかにおいて開始することができる。ブロック５０１では、図５のブロック４０２Ａで示すような４レベル基数検索が開始する。これは、図２の基数木１０８のセグメント１１２のレベルでの検索開始に対応する。ブロック５０４では、図５のブロック４０２Ｂで示すような３レベル基数検索が開始する。これは、図２の基数木１０８のセグメント１１３Ａ〜１１３Ｎのレベルでの検索開始に対応する。ブロック５０７では、図５のブロック４０２Ｃで示すような２レベル基数検索が開始する。これは、図２の基数木１０８のセグメント１１４Ａ〜１１４Ｎのレベルでの検索開始に対応する。ブロック５１０では、図５のブロック４０２Ｄで示すような１レベル基数検索が開始する。これは、図２の基数木１０８のセグメント１１５のレベルでの検索開始に対応する。有効アドレスのアドレス空間ＩＤに関連付けられたセグメント・サイズにより示される基数木の最低レベルで検索を開始することで、基数木の検索に必要なステップ数を削減し、これによって有効アドレスの変換を迅速化することができる。
【００１８】
ここで図６の方法５００のフローについて説明する。まずブロック５０１において、基数木１０８の第４（最高）レベルにおいて有効アドレスを検索して、基数木１０８の第３レベルにおけるもっと小さい一致セグメントを探す。次いでブロック５０２において、有効アドレスについて基数木１０８の第３レベルにおけるもっと小さい一致セグメントのＳＬＢエントリがＳＬＢ１０５に存在するか否かを判定する。第３レベルにおけるもっと小さい一致セグメントのＳＬＢエントリがＳＬＢ１０５に存在する場合、フローはブロック５０４に進む。他の場合、ブロック５０３において、第３レベルにおけるもっと小さい一致セグメントのＳＬＢエントリをＳＬＢに追加し、フローはブロック５０４に進む。ブロック５０４において、ブロック５０１で判定した第３レベルにおけるもっと小さい一致セグメントにおいて有効アドレスを検索して、第２レベルにおけるもっと小さい一致セグメントを探す。次いでブロック５０５において、第２レベルにおけるもっと小さい一致セグメントのＳＬＢエントリがＳＬＢ１０５に存在するか否かを判定する。第２レベルにおけるもっと小さい一致セグメントのＳＬＢエントリがＳＬＢ１０５に存在する場合、フローはブロック５０７に進む。他の場合、ブロック５０６において、もっと小さい一致セグメントのＳＬＢエントリをＳＬＢ１０５に追加し、フローはブロック５０７に進む。ブロック５０７において、ブロック５０４で判定した基数木１０８の第２レベルにおけるもっと小さい一致セグメントにおいて有効アドレスを検索して、基数木の第１レベルにおけるもっと小さい一致セグメントを特定する。次いでブロック５０８において、第１レベルにおけるもっと小さい一致セグメントのＳＬＢエントリがＳＬＢ１０５に存在するか否かを判定する。第１レベルにおけるもっと小さい一致セグメントのＳＬＢエントリがＳＬＢ１０５に存在する場合、フローはブロック５１０に進む。他の場合、ブロック５０９において、第１レベルにおけるもっと小さい一致セグメントのＳＬＢエントリをＳＬＢ１０５に追加し、フローはブロック５１０に進む。ブロック５１０において、ブロック５０７において判定した第１レベルにおけるもっと小さい一致セグメントにおいて有効アドレスを検索する。この時点で、図６の方法５００により説明した基数木１０８の検索が完了し、フローは図５の方法４００のブロック４０３に戻る。
【００１９】
図５に戻ると、フローはブロック４０３に進み、図６の方法５００において実行した検索の間に基数木１０８にヒットがあったか否かを判定する。ブロック４０３において基数木１０８に有効アドレスのヒットがあった場合、フローはブロック４０４に進み、ブロック４０４において、基数木１０８によって有効アドレスに与えられた変換をＴＬＢ１０６およびＥＲＡＴキャッシュ１０４に挿入し、これを用いてメイン・メモリ１０９にアクセスし、方法４００のフローは終了する。ブロック４０３において基数木のヒットがないと判定された場合、ブロック４０５において基数木ミス・フォルトが与えられ、方法４００のフローは終了する。これによって、基数木検索を示すタイプ・フィールド１１１Ｂを有する有効アドレスに適用された基数木検索は完了する。
【００２０】
図７は、一実施形態に従ったＨＴＰ検索のための方法６００のプロセス・フローを示す。ＳＬＢエントリ１１０のタイプ・フィールド１１１ＢがＨＴＰ検索を示す場合、方法６００は、図３の方法２００のブロック２０７の間にアドレス変換論理１０３によって実行される。最初にブロック６０１では、ＳＬＢ１０５において、有効アドレスに関連付けられたＳＬＢエントリ１１０のアドレス・フィールド１１１Ａから、有効アドレスに対応した仮想アドレスを抽出する。次いでブロック６０２では、ＴＬＢ１０６において仮想アドレスを検索する。次いでブロック６０３において、仮想アドレスがＴＬＢ１０６で見つかったか否かを判定する。ＴＬＢ１０６で仮想アドレスが見つかった場合、ブロック６０４において、ＴＬＢ１０６によって仮想アドレスに与えられた変換をＥＲＡＴキャッシュ１０４に挿入し、これをメモリ・アクセスのために用い、方法６００のフローは終了する。ＴＬＢに仮想アドレスが存在しない場合、フローはブロック６０５に進み、ＨＴＰ１０７において仮想アドレスを検索する。ＨＰＴ１０７は、いずれかの適切な方法を用いて検索することができる。次いでブロック６０６において、ＨＴＰ１０７で仮想アドレスが見つかったか否かを判定する。ＨＴＰ１０７で仮想アドレスが見つかった場合、ブロック６０７において、ＨＴＰ１０７によって仮想アドレスに与えられた変換をＴＬＢ１０６およびＥＲＡＴキャッシュ１０４に挿入し、これをメイン・メモリ１０９にアクセスするために用い、方法６００のフローは終了する。他の場合、ブロック６０８においてＨＰＴミス・フォルトを発行し、方法６００のフローは終了する。
【００２１】
上述のように、実施形態は、コンピュータ実施プロセスおよびこれらのプロセスを実行するための装置の形態で具現化することができる。一実施形態は、コンピュータ読み取り可能／使用可能媒体７０２上の図８に示すようなコンピュータ・プログラム７００を含むことができ、命令を含むコンピュータ・プログラム・コード論理７０４が製造品としての有形の媒体に具現化されている。コンピュータ読み取り可能／使用可能媒体７０２のための例示的な製造品は、フレキシブルディスク、ＣＤ−ＲＯＭ、ハード・ドライブ、ユニバーサル・シリアル・バス（ＵＳＢ）・フラッシュ・ドライブ、または他のいずれかのコンピュータ読み取り可能記憶媒体を含むことができ、コンピュータ・プログラム・コード論理７０４がコンピュータにロードされて実行されると、コンピュータは本発明を実行するための装置となる。実施形態が含むコンピュータ・プログラム・コード論理７０４は、例えば記憶媒体に記憶され、コンピュータにロードされるかまたはコンピュータにより実行されるかあるいはその両方であり、または、電気配線もしくはケーブルを介して、光ファイバによって、もしくは電磁放射によって等、何らかの伝送媒体を介して送信され、コンピュータ・プログラム・コード論理７０４がコンピュータにロードされて実行されると、コンピュータは本発明を実行するための装置となる。汎用マイクロプロセッサ上で実施された場合、コンピュータ・プログラム・コード論理７０４は、特定の論理回路を生成するようにマイクロプロセッサを構成する。
【００２２】
技術的な効果および利点は、適宜、異なるアドレス変換検索方式を用いることによって、コンピューティング・システム上で実行する異なるタイプのメモリ・アクセスまたはアプリケーションあるいはその両方についての性能向上を含む。
【００２３】
本明細書において用いた用語は、特定の実施形態を記載する目的のためだけのものであり、本発明を限定することは意図していない。本明細書において用いたように、単数形「１つの（ａ）、（ａｎ）、（ｔｈｅ）」は、文脈によって明らかに他の場合が示されない限り、複数形を含むことが意図されている。また、「含む」または「含んでいる」という言葉あるいはその両方は、本明細書において用いられた場合、述べた特性、整数、ステップ、動作、要素、またはコンポーネントあるいはそれら全ての存在を規定するが、１つ以上の他の特性、整数、ステップ、動作、要素、コンポーネント、またはそれらのグループあるいはそれら全ての存在または追加を除外するものではないことは、理解されよう。
【００２４】
以下の特許請求の範囲における全てのミーンズまたはステップ・プラス・ファンクション要素の対応する構造、材料、行為、および均等物は、具体的に特許請求したような他の特許請求した要素と組み合わせて機能を実行するためのいずれかの構造、材料、または行為を含むことが意図されている。本発明の記載は、例示および記述の目的のために提示したが、網羅的であることや、開示した形態に本発明を限定することは、意図していない。本発明の範囲および精神から逸脱することなく、当業者には多くの変更および変形が明らかであろう。実施形態は、本開示の原理および実際的な用途を最良に説明するため、更に、想定される特定の用途に適した様々な変更と共に様々な実施形態に関して当業者が本発明を理解することを可能とするために、選択し記載したものである。
【００２５】
当業者によって認められるように、本発明の態様は、システム、方法、またはコンピュータ・プログラムとして具現化することができる。従って、本発明の態様は、全体的にハードウェアの実施形態、全体的にソフトウェアの実施形態（ファームウェア、常駐ソフトウェア、マイクロコード等を含む）、または、ソフトウェアおよびハードウェアの態様を組み合わせた実施形態という形態を取ることができ、それらは全て本明細書において、「回路」、「モジュール」、または「システム」と一般的に称することができる。更に、本発明の態様は、具現化されたコンピュータ読み取り可能プログラム・コードを有する１つ以上のコンピュータ読み取り可能媒体において具現化されたコンピュータ・プログラムの形態を取ることも可能である。
【００２６】
１つ以上のコンピュータ読み取り可能媒体のあらゆる組み合わせを利用することができる。コンピュータ読み取り可能媒体は、コンピュータ読み取り可能信号媒体またはコンピュータ読み取り可能記憶媒体とすることができる。コンピュータ読み取り可能記憶媒体は例えば、限定ではないが、電子、磁気、光、電磁、赤外線、または半導体のシステム、装置、デバイス、または前述のもののいずれかの適切な組み合わせとすることができる。コンピュータ読み取り可能記憶媒体の更に具体的な例（非網羅的な列挙）は、以下を含む。すなわち、１本以上のワイヤを含む電気的接続、携帯型コンピュータ・ディスケット、ハード・ディスク、ランダム・アクセス・メモリ（ＲＡＭ）、読み取り専用メモリ（ＲＯＭ）、消去可能プログラマブル読み取り専用メモリ（ＥＰＲＯＭまたはフラッシュ・メモリ）、光ファイバ、携帯型コンパクト・ディスク読み取り専用メモリ（ＣＤ−ＲＯＭ）、光記憶デバイス、磁気記憶デバイス、または前述のもののいずれかの適切な組み合わせである。この文書の文脈において、コンピュータ読み取り可能記憶媒体は、命令実行システム、装置、またはデバイスによってまたはそれと接続して用いるためにプログラムを含有または記憶することが可能ないずれかの有形の媒体とすることができる。
【００２７】
コンピュータ読み取り可能信号媒体は、例えばベースバンドにおいてまたは搬送波の一部として、具現化されたコンピュータ読み取り可能プログラム・コードを有する伝播データ信号を含むことができる。かかる伝播信号は様々な形態のいずれかを取ることができ、それらは限定ではないが、電磁、光、またはそれらのいずれかの適切な組み合わせを含む。コンピュータ読み取り可能信号媒体は、コンピュータ読み取り可能記憶媒体でないが、命令実行システム、装置、またはデバイスによってまたはそれと接続して用いるためにプログラムを伝達、伝播、または転送することが可能ないずれかのコンピュータ読み取り可能媒体とすることができる。
【００２８】
コンピュータ読み取り可能媒体上で具現化されるプログラム・コードは、限定ではないが、無線、有線、光ファイバ・ケーブル、ＲＦ等、または前述のもののいずれかの適切な組み合わせを含むいずれかの適切な媒体を用いて伝送することができる。
【００２９】
本発明の態様の動作を実行するためのコンピュータ・プログラム・コードは、Ｊａｖａ、Ｓｍａｌｌｔａｌｋ、Ｃ＋＋等のオブジェクト指向プログラミング言語および「Ｃ」プログラミング言語または同様のプログラミング言語等の従来の手順プログラミング言語を含む１つ以上のプログラミング言語のいずれかの組み合わせにおいて記述することができる。プログラム・コードは、全体的にユーザのコンピュータ上で、部分的にユーザのコンピュータ上で、スタンドアロンのソフトウェア・パッケージとして、部分的にユーザのコンピュータ上でおよび部分的にリモート・コンピュータ上で、または全体的にリモート・コンピュータもしくはサーバ上で、実行することができる。後者の場合、リモート・コンピュータは、ローカル・エリア・ネットワーク（ＬＡＮ）またはワイド・エリア・ネットワーク（ＷＡＮ）を含むいずれかのタイプのネットワークを介してユーザのコンピュータに接続することができ、または、接続は、（例えばインターネット・サービス・プロバイダを用いてインターネットを介して）外部コンピュータに対して行うことができる。
【００３０】
本発明の実施形態に従った方法、装置（システム）、およびコンピュータ・プログラムのフローチャート図またはブロック図あるいはその両方を参照して、本発明の態様について上述している。フローチャート図またはブロック図あるいはその両方の各ブロック、およびフローチャート図またはブロック図あるいはその両方におけるブロックの組み合わせは、コンピュータ・プログラム命令によって実施可能であることは理解されよう。これらのコンピュータ・プログラム命令は、汎用コンピュータ、特殊目的コンピュータ、または他のプログラマブル・データ処理装置のプロセッサに提供されて機械を生成することができ、これによって、コンピュータまたは他のプログラマブル・データ処理装置のプロセッサによって実行される命令が、フローチャートまたはブロック図あるいはその両方のブロックまたは複数のブロックに規定された機能／行為を実施するための手段を生成するようになっている。
【００３１】
また、これらのコンピュータ・プログラム命令はコンピュータ読み取り可能媒体に記憶することができ、これによって、コンピュータ、他のプログラマブル・データ処理装置、または他のデバイスに特定の方法で機能するように指示することができ、これにより、コンピュータ読み取り可能媒体に記憶された命令が、フローチャートまたはブロック図あるいはその両方のブロックまたは複数のブロックに規定された機能／行為を実施する命令を含む製造品を生成するようになっている。
【００３２】
また、コンピュータ・プログラム命令を、コンピュータ、他のプログラマブル・データ処理装置、または他のデバイスにロードして、そのコンピュータ、他のプログラマブル装置、または他のデバイス上で一連の動作ステップを実行させてコンピュータ実施プロセスを生成することができ、これによって、コンピュータまたは他のプログラマブル装置上で実行する命令が、フローチャートまたはブロック図あるいはその両方のブロックまたは複数のブロックに規定された機能／行為を実施するためのプロセスを提供するようになっている。
【００３３】
上述のように、実施形態は、コンピュータ実施プロセスおよびこれらのプロセスを実行するための装置の形態で具現化することができる。実施形態において、本発明は、１つ以上のネットワーク要素によって実行されるコンピュータ・プログラム・コードにおいて具現化される。実施形態は、コンピュータ使用可能媒体上のコンピュータ・プログラムを含むことができ、命令を含むコンピュータ・プログラム・コード論理が製造品としての有形の媒体に具現化されている。コンピュータ使用可能媒体のための例示的な製造品は、フレキシブルディスク、ＣＤ−ＲＯＭ、ハード・ドライブ、ユニバーサル・シリアル・バス（ＵＳＢ）・フラッシュ・ドライブ、または他のいずれかのコンピュータ読み取り可能記憶媒体を含むことができ、コンピュータ・プログラム・コード論理がコンピュータにロードされて実行されると、コンピュータは本発明を実行するための装置となる。実施形態が含むコンピュータ・プログラム・コード論理は、例えば記憶媒体に記憶され、コンピュータにロードされるかまたはコンピュータにより実行されるかあるいはその両方であり、または、電気配線もしくはケーブルを介して、光ファイバによって、もしくは電磁放射によって等、何らかの伝送媒体を介して送信され、コンピュータ・プログラム・コード論理がコンピュータにロードされて実行されると、コンピュータは本発明を実行するための装置となる。
【００３４】
図面におけるフローチャートおよびブロック図は、本発明の様々な実施形態に従ったシステム、方法、およびコンピュータ・プログラムの可能な実施のアーキテクチャ、機能性、および動作を例示する。この点で、フローチャートまたはブロック図における各ブロックは、規定された論理機能（複数の機能）を実施するための１つ以上の実行可能命令を含むコードのモジュール、セグメント、または一部を表すことができる。また、いくつかの代替的な実施において、ブロックに明記した機能は、図面に明記した順序どおりでなく発生する場合があることに留意すべきである。例えば、関与する機能性に応じて、連続して示した２つのブロックは実際には実質的に同時に実行されることがあり、またはブロックは時に逆の順序で実行される場合がある。また、ブロック図またはフローチャート図あるいはその両方の各ブロック、およびブロック図またはフローチャート図あるいはその両方におけるブロックの組み合わせは、規定された機能もしくは行為を実行する特殊目的ハードウェア・ベースのシステム、または特殊目的ハードウェアおよびコンピュータ命令の組み合わせによって実施可能であることに留意すべきである。
【図１】
2015515057.tif 000003
【図２】
2015515057.tif 000004
【図３】
2015515057.tif 000005
【図４】
2015515057.tif 000006
【図５】
2015515057.tif 000007
【図６】
2015515057.tif 000008
【図７】
2015515057.tif 000009
【図８】
2015515057.tif 000010
【国際調査報告】
2015515057.tif 000011
2015515057.tif 000012
2015515057.tif 000013