(57)【要約】複数のソフトウェアプログラムに関する命令、定数値、他のタイプのデータを記憶するためのキャッシュ技術が記述される。キャッシュは複数のプログラムに関する記憶を提供し、複数のタイルに分割されている。各タイルは１つのプログラムに割り当て可能である。各プログラムは、プログラムのキャッシュ利用、利用可能なタイル、及び／又は他の要因に基づいて、任意の数のタイルが割り当てられる。キャッシュコントローラは、プログラムに割り当てられたタイルを識別し、当該キャッシュにアクセスするためのキャッシュアドレスを生成する。キャッシュは物理タイルに分割される。キャッシュコントローラは論理タイルをプログラムに割り当て、論理タイルをキャッシュ内の物理タイルにマッピングする。論理及び物理タイルの使用によりタイルの割り当てと管理とを簡略化する。【選択図】        図３
2009545080.tif 000002
【特許請求の範囲】
【請求項１】
装置であって、
複数のプログラムに対する記憶を提供するように動作可能であって、複数のタイルに分割されており、各タイルは１つのプログラムに割り当て可能なキャッシュと、
前記複数のプログラムに割り当てられたタイルを識別して、前記キャッシュにアクセスするためのキャッシュアドレスを生成するように動作可能なキャッシュコントローラと、を具備する装置。
【請求項２】
各プログラムは、少なくとも１つの連続するタイルが割り当てられている請求項１に記載の装置。
【請求項３】
各プログラムは、少なくとも１つのタイルが割り当てられ、直接マッピングに基づいて少なくとも１つのタイルにマッピングされる請求項１に記載の装置。
【請求項４】
各プログラムは、少なくとも１つのタイルが割り当てられ、N-wayセット連想マッピングに基づいて少なくとも１つのタイルにマッピングされる請求項１に記載の装置。
【請求項５】
前記キャッシュは、複数の物理タイルに分割されており、前記キャッシュコントローラは前記複数のプログラムに対して論理タイルを割り当て、前記論理タイルを前記物理タイルにマッピングする請求項１に記載の装置。
【請求項６】
前記キャッシュコントローラは、前記複数のプログラムに割り当てられた論理タイルを識別するように動作可能なルックアップテーブルを備えることを特徴とする請求項５に記載の装置。
【請求項７】
各プログラムは、少なくとも１つの連続する論理タイルが割り当てられ、前記ルックアップテーブルは、第１の論理タイルを記憶し、前記論理タイルの数は各プログラムに割り当てられている請求項６に記載の装置。
【請求項８】
前記キャッシュコントローラは、前記論理タイルの前記物理タイルへのマッピングを記憶するように動作可能なルックアップテーブルを備える請求項５に記載の装置。
【請求項９】
前記キャッシュコントローラは、プログラムに関するプログラムカウンタを受け取って、前記プログラムカウンタに対応する論理タイルアドレスを提供するように動作可能なアドレス生成器を備える請求項５に記載の装置。
【請求項１０】
前記アドレス生成器はさらに、前記プログラムの、前記プログラムに割り当てられた少なくとも１つの論理タイルへの直接マッピングに基づいて前記プログラムカウンタに関するタグを決定する請求項９に記載の装置。
【請求項１１】
前記キャッシュコントローラは、プログラムに関するプログラムカウンタを受け取って、前記プログラムカウンタからプログラム部分に関するベースアドレスを取得し、前記ベースアドレスと、前記プログラムに割り当てられた第１の論理タイルと、前記プログラムに割り当てられた論理タイルの数と、によって論理タイルアドレスを引き出し、前記ベースアドレスと、前記プログラムに割り当てられた論理タイルの数と、によって前記プログラムカウンタに関するタグを引き出す、ように動作可能なアドレス生成器を備える請求項５に記載の装置。
【請求項１２】
前記キャッシュコントローラは、起動中のプログラムの指示を受け取って、少なくとも１つのタイルを前記プログラムに割り当てる請求項１に記載の装置。
【請求項１３】
前記キャッシュコントローラは、退避するプログラムの指示を受け取って、少なくとも１つのタイルに少なくとも１つの他のプログラムを再割り当てする請求項１２に記載の装置。
【請求項１４】
前記キャッシュは、
前記複数のプログラムに関する記憶を提供するように動作可能であって、前記複数のタイルに分割されている第１のメモリと、
前記第１のメモリにおける前記複数のタイルに関するタグを記憶するように動作可能な第２のメモリと、を備える請求項１に記載の装置。
【請求項１５】
前記キャッシュは、前記複数のプログラムに関する命令を記憶するように動作可能である請求項１に記載の装置。
【請求項１６】
前記キャッシュは、前記複数のプログラムに関する定数値を記憶するように動作可能な請求項１に記載の装置。
【請求項１７】
集積回路であって、
複数のプログラムに関する記憶を提供するように動作可能であって、複数のタイルに分割されており、各タイルは１つのプログラムに割り当てられているキャッシュと、
前記複数のプログラムに割り当てられたタイルを識別して、前記キャッシュにアクセスするためのキャッシュアドレスを生成するように動作可能なキャッシュコントローラと、を具備する集積回路。
【請求項１８】
前記キャッシュは、複数の物理タイルに分割され、前記キャッシュコントローラは論理タイルを前記複数のプログラムに割り当て、前記論理タイルを前記物理タイルにマッピングする請求項１７に記載の集積回路。
【請求項１９】
前記キャッシュコントローラは、プログラムに関するプログラムカウンタを受け取って、前記プログラムカウンタに基づいて論理タイルアドレスを引き出し、前記論理タイルアドレスと論理タイルの物理タイルへのマッピングとに基づいて物理タイルアドレスを生成する請求項１８に記載の集積回路。
【請求項２０】
方法であって、
キャッシュ内の複数のタイルを複数のプログラムに割り当てることであって、各タイルは１つのプログラムに割り当て可能であることと、
前記複数のプログラムのうちの１つのプログラムからのアクセス要求を受け取ることと、
前記プログラムに割り当てられた少なくとも１つのタイルを識別することと、
前記プログラムに割り当てられた少なくとも１つのタイルに基づいて、キャッシュアドレスを生成することと、を備える方法。
【請求項２１】
前記キャッシュ内の複数のタイルを複数のプログラムに割り当てることは、
論理タイルを前記複数のプログラムに割り当てることと、
前記論理タイルを前記キャッシュ内の物理タイルにマッピングすることと、を備える請求項２０に記載の方法。
【請求項２２】
前記キャッシュアドレスを生成することは、
前記プログラムに関するプログラムカウンタを受け取ることと、
前記プログラムカウンタに基づいて論理タイルアドレスを引き出すことと、
前記論理タイルアドレスと、論理タイルの物理タイルへのマッピングとに基づいて物理タイルアドレスを生成することと、を備える請求項２１に記載の方法。
【請求項２３】
装置であって、
キャッシュ内の複数のタイルを複数のプログラムに割り当てるための手段であって、各タイルは１つのプログラムに割り当て可能な手段と、
前記複数のプログラムのうちの１つのプログラムからのアクセス要求を受け取るための手段と、
前記プログラムに割り当てられた少なくとも１つのタイルに基づいて、キャッシュアドレスを生成するための手段と、を備える装置。
【請求項２４】
前記キャッシュ内の複数のタイルを前記複数のプログラムに割り当てるための手段は、
論理タイルを前記複数のプログラムに割り当てるための手段と、
前記論理タイルを前記キャッシュ内の物理タイルにマッピングするための手段と、を備える請求項２３に記載の装置。
【請求項２５】
前記キャッシュアドレスを生成するための手段は、
前記プログラムに関するプログラムカウンタを受け取るための手段と、
前記プログラムカウンタに基づいて論理タイルアドレスを引き出すための手段と、
前記論理タイルアドレスと、論理タイルの物理タイルへのマッピングとに基づいて、物理タイルアドレスを生成するための手段と、を備える請求項２４に記載の装置。
【請求項２６】
ワイヤレス装置であって、グラフィックス演算を実行するように動作可能なグラフィックスプロセッサを備え、前記グラフィックスプロセッサは、
複数のプログラムに関する命令を記憶するように動作可能であって、複数のタイルに分割された命令キャッシュと、
前記複数のプログラムに割り当てられたタイルを識別して、前記命令キャッシュにアクセスするためのキャッシュアドレスを生成するように動作可能なキャッシュコントローラと、を具備するワイヤレス装置。
【請求項２７】
前記命令キャッシュは、複数の物理タイルに分割されており、前記キャッシュコントローラは論理タイルを複数のプログラムに割り当てて、前記論理タイルを前記物理タイルにマッピングする請求項２６に記載のワイヤレス装置。
【請求項２８】
前記キャッシュコントローラは、プログラムに関するプログラムカウンタを受け取って、前記プログラムカウンタに基づいて論理タイルアドレスを引き出し、前記論理タイルアドレスと論理タイルの物理タイルへのマッピングとに基づいて物理タイルアドレスを生成する請求項２７に記載のワイヤレス装置。
【発明の詳細な説明】
【技術分野】
【０００１】
背景
１．分野
本開示は、概して、電子工学に関し、特に、複数のソフトウェアプログラムのためのストレージを提供する技術に関している。
【背景技術】
【０００２】
２．背景
多くの電子装置は、複数のソフトウェアプログラムを並行して実行することが可能である。例えば、グラフィックプロセッサは、ビデオゲーム、グラフィックス、イメージングなどのアプリケーションのために複数のグラフィックスプログラムを実行することができる。各プログラムは一連の命令である。プログラムカウンタは各プログラムに対して維持され、当該プログラムに関して実行される現在の命令を指し示す。
【０００３】
実行されるプログラムは大きなサイズであり、大容量ユニットに記憶される。動作速度を改善するために、各プログラムの小部分が大容量ユニットから、プロセッサにより近い位置に配置された高速メモリである、命令キャッシュにロードディングされる。命令キャッシュは実行させるすべてのプログラムに関する命令を記憶する。命令キャッシュの利用を改善するために、プログラムは当該キャッシュ内で同一のアドレス空間を共有する。このことは、各キャッシュ位置が任意のプログラムに関する命令を記憶することを可能にする。
【０００４】
１つのキャッシュに複数のプログラムのための命令を記憶することに関する主な課題は、プログラム間での“命令スラッシング”（instruction thrashing）である。命令スラッシングは、１つ以上のプログラムがキャッシュの同一の位置を求めて競合し、命令が連続的に互いに上書きされてしまう現象である。命令スラッシングは、過剰なキャッシュミスにつながる。キャッシュミスは、キャッシュ内に所望の命令が見つからない場合に発生する。キャッシュは概して最初に命令で満たされ、次にその命令が取り出されて実行されるようになっているので、キャッシュミスは命令の実行に関して遅延を発生させる。命令スラッシングは影響のあるすべてのプログラムのパフォーマンスに関して悪い影響を与える。
【発明の概要】
【０００５】
複数のソフトウェアプログラムに関する命令、定数値、他のタイプのデータをキャッシュに記憶するための技術が以下に記述される。この技術は、プログラム間のスラッシングを防止するとともに、プログラム間で利用可能なキャッシュ記憶空間を効率よく共有することを可能にする。
【０００６】
一実施形態において、装置は、キャッシュとコントローラをとを含む。キャッシュは複数のプログラムのための記憶（ストレージ）を提供し、複数のタイルに分割されている。各タイルは１つのプログラムに割り当て可能である。各プログラムは、プログラムのキャッシュ利用、利用可能なタイル、及び／又は他の要因に基づいて任意の数のタイルが割り当てられる。キャッシュコントローラは、プログラムに割り当てられたタイルを識別して当該キャッシュにアクセスするためのキャッシュアドレスを生成する。
【０００７】
一実施形態において、キャッシュは複数の物理タイルに分割される。キャッシュコントローラは、プログラムに対して論理タイルを割り当て、当該論理タイルをキャッシュ内の物理タイルにマッピングする。論理タイルと物理タイルとを使用することによってプログラムに対するタイルの割り当てとタイルの管理とを簡略化する。キャッシュコントローラはプログラムに関するプログラムカウンタを受け取って、当該プログラムカウンタに基づいて論理タイルアドレスを引き出し、この論理タイルアドレスと論理タイルの物理タイルへのマッピングとに基づいて物理タイルアドレスを生成し、物理タイルアドレスによりキャッシュアドレスを形成する。次に、キャッシュコントローラによって決定されたキャッシュアドレスにおいて、所望の命令がキャッシュから取り出される。
【図面の簡単な説明】
【０００８】
本発明の側面および実施形態が図面を参照した以下の詳細な説明からより明らかになる。同一のものを示すのに同一の参照符号が明細書全体にわたって用いられる。
【図１】図１は、グラフィックシステムのブロック図を示す。
【図２】図２は、グラフィックシステム内のシェーダコア(shader core)のブロック図である。
【図３】図３は、タイルアーキテクチャを備えるキャッシュに関する、論理タイル及び物理タイルを示す。
【図４】図４は、シェーダコア内の、スレッドスケジューラおよび命令キャッシュを示す。
【図５】図５は、論理タイルルックアップテーブルと物理アドレスルックアップテーブルとを示す。
【図６】図６は、プログラムの論理タイルへの直接マッピングを示す。
【図７】図７は、命令キャッシュに対するアドレス生成を示す。
【図８】図８は、命令キャッシュ内のタグＲＡＭ及び命令ＲＡＭを示す。
【図９】図９は、ワイヤレス装置のブロック図を示す。
【発明を実施するための形態】
【０００９】
ここでの語句”典型的”は、一例、一具体例、例示として用いられる。ここに一例として記述される実施形態あるいは設計は、他の実施形態あるいは設計と比較して必ずしもより好ましいと解釈させるべきではない。
【００１０】
ここに記述されるキャッシング技術は、複数のソフトウェアプログラムを並行して実行可能な種々のシステム及び装置に関して用いられる。例えば、当該技術は、計算装置、通信装置などに関して用いることができる。説明を明確にするためにここでは、特にグラフィックシステムに関して記述する。
【００１１】
図１は、グラフィックシステム１００のブロック図であり、スタンドアロンシステムあるいは計算システム、ワイヤレス通信装置（例えば携帯電話）などの大型のシステムの一部である。グラフィックシステム１００は、０〜Ｐ−１までのプログラムＩＤをもつＰ個のグラフィックプログラム／アプリケーション１１０ａ〜１１０ｐをそれぞれ支持する。ここで、Ｐは任意の整数値である。プログラム１１０ａ〜１１０ｐは並列に実行され、ビデオゲーム、グラフィックス及び／又は他のアプリケーションに関するものである。
【００１２】
グラフィックプロセッサ１２０は、プログラム１１０ａから１１０ｐに関して処理を実行する。グラフィックプロセッサ１２０は例えば自動的にかつ当該プログラムに透過的に各プログラムの処理を一連のスレッドに分割する。スレッド（又は実行のスレッド）は１つ以上の命令の組により実行される特別なタスクを示す。スレッドは１つのプログラムが異なるユニットによって実行可能な複数のタスクをもつことを可能にするとともに、異なるプログラムが資源を共有することを可能にする。
【００１３】
図１に示す実施形態において、グラフィックプロセッサ１２０は、シェーダコア（shader core）１３０、テクスチャエンジン１４０及びキャッシュメモリシステム１５０を含む。コアは概して集積回路内の処理ユニットを意味する。”コア”、”エンジン”、”マシン”、”プロセッサ”及び”処理ユニット”なる述語は交互に用いられる。”コア”は概して集積回路内の処理ユニットを意味する。シェーダコア１３０は、ライティング(lighting)、シャドウイング（shadowing）などを含む高度に複雑なグラフィック処理である、シェーディング（shading）などのグラフィック処理を実行する。テクスチャエンジン１４０は、テクスチャイメージの色による画素の色の変更処理を含む他の複雑なグラフィック処理であるテクスチャマッピングなどのグラフィック処理を実行する。キャッシュメモリシステム１５０は、シェーダコア１３０及びテクスチャエンジン１４０に関する命令及び／又はデータを記憶可能な高速メモリである１つ以上のキャッシュを含む。グラフィックプロセッサ１２０は、他の処理及び制御ユニット、エンジン及びメモリを含む。グラフィックプロセッサ１２０は、オープングラフィックスライブラリ（ＯｐｅｎＧＬ）、Direct3Dなどのソフトウェアインタフェースを実装する。ＯｐｅｎＧＬは、”ＯｐｅｎＧＬ（登録商標）グラフィックシステム：仕様”なる名称で、バージョン２．０、２００４年１０月２２日付けの文書に記述されている。この文書は一般に公開されている。
【００１４】
メインメモリ１６０は、グラフィックスプロセッサ１２０からより遠くの位置（例えばチップの外）に配置された、大型で低速のメモリである。メインメモリ１６０は、キャッシュメモリシステム１５０内のキャッシュ内にロードされる命令及びデータを記憶する。メインメモリ１６０は、グラフィックスプロセッサ１２０によって実行されるすべてのプログラムを記憶する。
【００１５】
図２は、図１におけるシェーダコア１３０の実施形態のブロック図である。シェーダプログラム１３０内において、マルチプレクサ（Ｍｕｘ）２０８はプログラム１１０ａ〜１１０ｐからスレッドを受け取って、これらのスレッドをスレッドスケジューラ及びコンテクストレジスタ２１０に供給する。スレッドスケジューラ２１０は、スレッドの実行をスケジュール及び管理するために種々の機能を実行する。スレッドスケジューラ２１０は、新たなスレッドを受け入れるかどうかを決定し、各受け入れたスレッドに関するレジスタマップテーブルを生成し、当該スレッドに対して資源を割り当てる。レジスタマップテーブルは、論理的レジスタアドレスと物理レジスタファイルアドレス間のマッピングを示す。各スレッドに関して、スレッドスケジューラ２１０は、当該スレッドに対して要求される資源が準備できているかどうかを決定し、当該スレッドに関する資源（例えば命令、レジスタファイルあるいはテクスチャリード）が準備できていないならば、当該スレッドをスリープキューへとプッシュし、すべての資源が準備できたときに、当該スレッドをスリープキューからアクティブキューへ移行させる。スレッドスケジューラ２１０は、当該スレッドに関する資源を同期させるためにロードコントロールユニット２１２と接続する。
【００１６】
スレッドスケジューラ２１０はスレッドの実行をも管理する。スレッドスケジューラ２１０はスレッドの実行をも管理する。スレッドスケジューラ２１０は、各スレッドに関する命令を命令キャッシュ２２０からフェッチし、必要ならば各命令をデコードし、スレッドに関するフロー制御を実行する。スレッドスケジューラ２１０は、実行のためにアクティブスレッドを選択し、選択されたスレッド間でリード／ライトポートの競合があるかどうかを調べ、競合がなければ、１つのスレッドに関する命令を算術論理ユニット（ＡＬＵ）２１６に送信するとともに、他のスレッドに関する命令をロード制御ユニット２１２に送信する。スレッドスケジューラ２１０は、各スレッドに関してプログラムカウンタを維持し、命令が実行されるかあるいはプログラムフローが変更されたときにこのカウンタを更新する。スレッドスケジューラ２１０はまた、欠落している命令をフェッチするとともに完了したスレッドを除去するための要求を発行する。
【００１７】
命令キャッシュ２２０は、プログラム１１０ａ〜１１０ｐに関する命令を記憶する。これらの命令は、各スレッドに関して実行されるべき特定の演算を示す。各演算は、算術演算、基本演算、メモリアクセス演算などである。命令キャッシュ２２０は、ロード制御ユニット２１２を介して、キャッシュメモリシステム１５０及び／又はメインメモリ１６０（必要に応じて）からの命令によってロードされる。
【００１８】
ＡＬＵ２１６は、加算、減算、乗算、積和、絶対値、否定、比較、飽和などの算術演算を実行する。ＡＬＵ２１６はまた、ＡＮＤ、ＯＲ、ＸＯＲなどの論理演算を実行する。ＡＬＵ２１６はまた、例えば整数から浮動小数点数へのフォーマット変換およびその逆方向の変換を実行する。定数バッファ２１８は、ＡＬＵ２１６によって使用される（スケールファクタ、フィルタ重みなどの）定数を記憶する。
【００１９】
ロード制御ユニット２１２は、シェーダコア１３０内で種々のユニットに関して命令及びデータのフローを制御する。ロード制御ユニット２１２は、キャッシュメモリシステム１５０と接続して、命令キャッシュ２２０、定数バッファ２１８及びレジスタファイルバンク／出力バッファ２２２を、キャッシュメモリシステム１５０からの命令及びデータによってロードする。ロード制御ユニット２１２はまた、出力バッファ２２２内のデータをキャッシュメモリシステム１５０にセーブする。ロード制御ユニット２１２はまた、テクスチャエンジン１４０に命令を供給して、テクスチャエンジンから結果を受け取る。出力バッファ２２２は、ＡＬＵ２１６及びテクスチャエンジン１４０からの中間結果と最終結果とを記憶する。デマルチプレクサ（Demux）２２４は出力バッファ２２２から実行されたスレッドに関する最終結果を受け取るとともに、これらの結果をプログラム１１０ａ〜１１０ｐに供給する。
【００２０】
一実施形態において、命令キャッシュ２２０は、キャッシュを共有しているプログラム間での命令スラッシングを回避可能なタイルアークテクチャを実装している。タイルアーキテクチャはまた、利用可能なキャッシュ記憶空間をすべてのプログラム間で効率よく共有することを可能にする。このタイルアーキテクチャは、命令キャッシュ２２０を複数（Ｔ個）のタイルに分割する。一実施形態において、Ｔ個のタイルは同じサイズをもち、各タイルは所定数のキャッシュラインを含む。キャッシュラインは任意のサイズであり、任意の数の命令を記憶する。キャッシュラインは概して、１クロックサイクル内で他のメモリから満たされるかあるいは他のメモリへ記憶される。一実施形態において、各プログラムは、プログラムのキャッシュ利用および利用可能なタイルに基づいて１つ以上のタイルが割り当てられる。他の実施形態において、タイルは異なるサイズをもち、固定あるいは変更可能とされる。一実施形態において、各プログラムは、プログラムのキャッシュ利用および利用可能なタイルに基づいて適当なサイズの１つのタイル（あるいは複数のタイル）が割り当てられる。説明を明確にするために、以下の記述ではＴ個の等しいサイズのタイルをもつ実施形態について説明する。また、以下の記述では、各タイルはＫ個の命令を記憶可能であることを仮定する。ここでＫは任意の値である。
【００２１】
図３は命令キャッシュ２２０に関する論理タイル及び物理タイルの実施形態を示す。バーチャル（仮想）キャッシュ３１０は、０〜Ｔ−１のＴ個の論理タイルを含む。各プログラムは任意の数の連続する論理タイルが割り当てられる。図３に示す例では、プログラム０は論理タイル０及び１が割り当てられ、プログラム１は論理タイル２〜５が割り当てられ、以下同様である。
【００２２】
命令キャッシュ２２０はプログラムに関する命令を記憶する物理キャッシュ３２０を実装する。物理キャッシュ３２０は０〜Ｔ−１のＴ個の物理タイルを含み、各物理タイルはＫ個の命令を記憶可能である。各論理タイルは１つの物理タイルにマッピングされる。いくつかの論理タイルに関する例示的マッピングが図３に示されている。この例において、物理タイル０は論理タイル１に関する命令を記憶し、物理タイル１は論理タイルＴ−２に関する命令を記憶し、以下同様である。
【００２３】
論理タイルと物理タイルを使用することによって、プログラムへのタイルの割り当てとタイルの管理とを簡略化することができる。例えば、あるプログラムは、物理タイルの間で命令を転送することなしに、単にルックアップテーブルを更新することによって、さらなるより少ないあるいは異なる論理タイルが割り当てられる。各プログラムに対する連続する論理タイルの割り当ては、以下に述べるように、アドレスの生成を簡略化する。
【００２４】
図４は、図３に示すスレッドスケジューラ２１０及び命令キャッシュ２２０の実施形態である。スレッドスケジューラ２１０内において、スレッドマネージャ４１０は実行すべきスレッドを受け取って当該スレッドに対するプログラムＩＤとプログラムカウンタを提供する。プログラムＩＤはスレッドが属するプログラムを識別する。プログラムカウンタは当該スレッドに関して実行すべき現在の命令を示すものであり、所望の命令と呼ぶ。
【００２５】
キャッシュコントローラ４２０は、論理及び物理タイルを管理し、キャッシュアドレスを生成する。キャッシュコントローラ４２０内で、論理タイルルックアップテーブル（ＬＵＴ）４３０はプログラムＩＤを受け取って第１の論理タイルと当該プログラムに割り当てられた論理タイルの数とを提供する。図３に示す例では、ルックアップテーブル４３０は、第１の論理タイルとして”２”、プログラム１に関して割り当てられたタイルの数として”４”を提供する。アドレス生成器４４０はプログラムカウンタと、第１の論理タイルと、割り当てられたタイルの数とを受け取る。アドレス生成器４４０は、所望の命令を含む論理タイルのアドレスと、所望の命令に関するこの論理タイル内のオフセットと、命令タグとを提供する。物理アドレスルックアップテーブル４５０は、論理タイルアドレスを受け取ってこの論理タイルアドレスにマッピングされた物理タイルのアドレスを提供する。
【００２６】
以下に、キャッシュコントローラ４２０内部のユニットの動作について説明する。
【００２７】
命令キャッシュ２２０は、命令ランダムアクセスメモリ（ＲＡＭ）４６０と、タグＲＡＭ４７０と、比較ロジック４８０とを含む。タグＲＡＭ４７０は、論理タイルアドレスを受け取って、当該論理タイルアドレスに関して命令ＲＡＭ４６０内に現在記憶されているプログラムの部分を示すタグを提供する。比較ロジック４８０はタグＲＡＭ４７０から記憶されたタグと、アドレス生成器４４０から命令タグとを受け取る。比較ロジック４８０は２つのタグを比較して２つのタグが等しいのであればキャッシュヒットを提供し、等しくない場合にはキャッシュミスを提供する。キャッシュヒットは所望の命令を含むプログラム部分が命令ＲＡＭ４６０に記憶されていることを意味する。スレッドスケジューラ２１０は比較ロジック４８０からキャッシュミス／ヒット識別子を受け取って、キャッシュヒットがあるならば所望の命令の実行をスケジュールするとともに、キャッシュミスがあるならば命令の実行を停止する。以下に、命令キャッシュ２２０内部のユニットの動作について説明する。
【００２８】
図５は、図４に示すキャッシュコントローラ４２０内部の論理タイルルックアップテーブル４３０及び物理アドレスルックアップテーブル４５０の実施形態を示す。
【００２９】
この実施形態において、論理タイルルックアップテーブル４３０はＰ個のプログラムに対してＰ個のエントリ、各プログラムに対して１個のエントリを含む。Ｐ個のエントリはプログラムＩＤによってインデクス化される。各プログラムに関するエントリは当該プログラムに割り当てられた第１の論理タイルに関するフィールドを含むとともに、当該プログラムに割り当てられた論理タイルの数に関する他のフィールドを含む。図３に示される例において、プログラム０は論理タイル０から始まる４つの論理タイルが割り当てられ、プログラム２は論理タイル６から始まる８つの論理タイルが割り当てられる。以下同様である。アドレス生成を簡略化するために各プログラムは連続的は論理タイルが割り当てられる。しかしながら、プログラムは任意の順番の論理タイルを割り当てることができ、例えば論理タイル０は任意のプログラムに割り当てられる。
【００３０】
図５に示す実施形態において、物理アドレスルックアップテーブル４５０はＴ個の論理タイルに関してＴ個のエントリ、各論理タイルに関して１個のエントリを含む。Ｔ個のエントリは論理タイルアドレスによってインデクス化される。各論理タイルに関するエントリは論理タイルがマッピングされる物理タイルを示している。図３に示す例では、論理タイル０は物理タイル３にマップされ、論タイル１は物理タイル０にマップされ、論理タイル２は物理タイルｉにマップされ、論理タイル３は物理タイルＴ−３にマップされる。以下同様である。ルックアップテーブル４３０及び４５０は以下に示すように、プログラムがさらなるより少ない及び／又は異なる論理タイルが割り当てられるときにはいつでも更新される。
【００３１】
図６は直接マッピングスキームに関してその割り当てられた論理タイルへのあるプログラムの例示的マッピングを示している。プログラムはＬ個の論理タイルが割り当てられ、Ｌは任意の正の整数値である。しかしながら、アドレスの計算を簡単にするために、Ｌは２のべき乗すなわち２、４、８、…とする。概して、Ｌが割り当てられた論理タイルはＴ個の利用可能な論理タイルの一部である。以下の説明を簡単にするために、Ｌが割り当てられた論理タイルは論理タイル０〜Ｌ−１とする。
【００３２】
プログラムは連続する数が付された部分に分割される。各部分は１つの物理タイルのサイズに等しい。直接マッピングスキームにおいては、プログラムの各部は１つの割り当てられた論理タイルにマッピングされる。例えば、プログラムの部分０、Ｌ、２Ｌなどは割り当てられた論理タイル０にマッピングされ、プログラムの部分１、Ｌ＋１、２Ｌ＋１などは論理タイル１などに割り当てられる。概して、プログラム部分ｘは割り当てられた論理タイルｙにマッピングされ、ここでｙ＝（ｘ  ＭＯＤ  Ｌ）であり、ＭＯＤ  Ｌはmodulo-Lの演算を意味する。
【００３３】
さらにプログラムの部分はタグによって識別される。部分０〜Ｌ−１は０のタグをもち、部分Ｌ〜２Ｌ−１は１のタグをもつ。以下同様である。タグＲＡＭが各論理タイルに記憶されているプログラム部分のタグを記憶している。図６に示される例では、タグＲＡＭは、論理タイル０が２のタグをもつプログラム部分２Ｌを記憶するとともに、論理タイル１が０のタグをもつプログラム部分１を記憶することを示している。
【００３４】
直接マッピングスキームは、所望の命令が命令キャッシュ２２０に記憶されているかどうかを決定するために、比較演算の数を減らす。所望の命令はただ１つの割り当てられた論理タイルに記憶されるので、所望の命令が命令キャッシュ２２０に記憶されるかどうかを決定するために、ただ１つの比較演算が実行される。他の実施形態においては、Ｎ-wayセット連想（Ｎ-way set associate）スキームが用いられ、プログラムの各部分はＮ個の可能な論理タイルの任意の１つにマッピングされる。ここでＮ＞１である。所望の命令が当該命令に関するＮ個の可能な論理タイルのいくつかが記憶されるかどうかを決定するために、Ｎ個までの比較演算が実行される。説明を明確に行うために以下では直接マッピングスキームについて説明する。
【００３５】
図７は命令キャッシュ２２０に関するアドレス生成を示す。プログラムカウンタは所定数のビットを含み、ｋ個の最下位ビット（ＬＳＢ）とｍ個の最上位ビット（ＭＳＢ）とに分割される。ここでｋは、各物理タイルのサイズによって決定され、Ｋ＝２k で与えられる。ここでＫは命令の数の単位で与えられるタイルサイズである。ｍはプログラムカウンタの残りのビットである。
【００３６】
プログラムカウンタのｋ個のＬＳＢは物理タイルに関するオフセットとして用いられる。プログラムカウンタのｍ個のＭＳＢはベースアドレスとして用いられる。
【００３７】
ベースアドレスは所望の命令を含むプログラム部分（あるいは簡単には所望のプログラム部分）の開始アドレスである。ベースアドレスは所望のプログラム部分と当該部分のタグを含む論理タイルを決定するために用いられる。
【００３８】
所望のプログラム部分がマッピングされる論理タイルは以下のように決定される。
【００３９】
論理タイルアドレス＝（ベースアドレスＭＯＤ  Ｌ）＋最初の論理タイルアドレス
式（１）
この論理タイルに関連する物理タイルは、論理タイルアドレスを以下のようにルックアップすることによって獲得される。
【００４０】
物理タイルアドレス＝ＬＵＴ（論理タイルアドレス）                          式（２）
ここでＬＵＴ（）はルックアップ演算を表している。
【００４１】
所望のプログラム部分のタグは以下のように決定される。
【００４２】
命令タグ＝ベースアドレスＤＩＶ  Ｌ                                        式（３）
ここで、ＤＩＶは商（quatient）を提供する演算を示す。Ｌが２のべき乗、すなわち、Ｌ＝２ｌ であるならば、式（１）のＭＯＤ演算はベースアドレスのｌ個のＬＳＢを提供する。また、式（３）のＤＩＶ演算はベースアドレスの残りのｍ−ｌ個のＭＳＢを提供する。
【００４３】
キャッシュアドレスは物理タイルアドレスをオフセットと連結することによって以下の通り取得される。
【００４４】
キャッシュアドレス＝物理タイルアドレス‖オフセット                        式（４）
ここで、‖は、連結演算を示す。
【００４５】
図８は、図４に示される命令キャッシュ２２０内部のタグＲＡＭ４７０の実施形態である。タグＲＡＭ４７０はＴ個の論理タイルに関するＴ個のエントリ、各論理タイルに関して１つのエントリを含む。Ｔ個のエントリは、図４に示されるアドレス生成器４４０からの論理タイルアドレスによってインデクス化される。図８に示される実施形態において、各論理タイルに関するエントリはタグ及び有効ビットを含む。タグは論理タイル（実際には論理タイルに関連する物理タイルに記憶されたプログラム部分のベースアドレス）を示す。図３に示す例において、論理タイル０に関するエントリは物理タイル３に記憶されたプログラム部分のタグを記憶し、論理タイル１に関するエントリは物理タイル０に記憶されたプログラム部分のタグを記憶する。以下同様である。各論理タイルに関する有効ビットはその論理タイルが現在プログラム部分を記憶するかどうかを示している。あるプログラムが新たな論理タイルを割り当てられたときに、有効ビットは、論理タイルに関する有効なデータがないことを示すために”０”に設定される。有効ビットは”１”に設定され、タグは論理タイルをプログラム部分で満たした後に更新される。
【００４６】
所望の命令が所定の論理タイルに記憶されているかどうかを決定するために、その論理タイルに関するタグはタグＲＡＭ４７０から取得されて、アドレス生成器４４０からの命令タグと比較される。２つのタグが一致しかつ有効ビットが”１”ならば、キャッシュヒットがあったということになる。この場合には、所望の命令が論理タイルに記憶され、この命令に関するキャッシュアドレスで命令ＲＡＭ４６０から回収される。キャッシュアドレスは正当な物理タイルアドレスと当該タイルに関するオフセットとを含む。キャッシュミスがあった場合には、物理タイルは所望の命令を含むプログラム部分により満たされる。次に関連する論理タイルに関するタグは物理タイル内にロードされたプログラム部分のタグによって更新される。
【００４７】
一例では、アドレス生成器４４０は、所望の命令は論理タイルｂにマッピングされたプログラム部分ａ内に存在することを示している。物理アドレスルックアップテーブル４５０は、論理タイルｂは物理タイルｃにマッピングされたことを示す。タグＲＡＭ４７０が、論理タイルｂに記憶されたプログラム部分がタグａをもつことを示しているならば、キャッシュヒットが存在することになり、所望の命令が物理タイルｃから回収される。逆に、タグＲＡＭ４７０が、論理タイルｂに記憶されたプログラム部分がａ以外のタグをもつことを示しているならば、キャッシュミスが存在することになる。プログラム部分ａは物理タイルｃ内にロードされ、タグＲＡＭ４７０は論理タイルｂに関するタグａを記憶するために更新される。
【００４８】
図４及び図８に示される実施形態において、タグＲＡＭ４７０におけるタグは論理タイルアドレスによりインデクス化される。この実施形態では、論理タイルアドレスが物理タイルアドレスに先立って利用できるので、タグＲＡＭ４７０内のタグをより早い時期にルックアップすることを可能にする。他の実施形態においては、タグＲＡＭ４７０内のタグは、物理タイルアドレスによってインデクス化される。タグがインデクス化される手順は、タグが、論理タイルに関するプログラムの割り当て、再割り当て、割り当ての解除時に、どのようにして更新されるのかについて影響を与える。
【００４９】
図８はまた、命令キャッシュ２２０内の命令ＲＡＭ４４０の実施形態を示す。この実施形態では、各キャッシュラインは２つのエントリを含み、各エントリは１つの命令を記憶する。各タイルは、０〜Ｋ−１のオフセットに関連する、Ｋ個のエントリに関してＫ／２個のキャッシュラインを含む。図７において生成されたキャッシュアドレスは、命令ＲＡＭ４６０内の特定のタイルに関する物理タイルアドレスと、このタイル内の特定のエントリに関するオフセットを含む。概して、タイルは任意の数のキャッシュラインを含み、各キャッシュラインは任意のサイズであり、任意の数の命令を記憶する。
【００５０】
論理タイルは、実行中のプログラムの数、これらのプログラムのキャッシュ利用、利用可能な論理タイル及び／または他の要因に基づいて、プログラムに対して動的に割り当てられるか割り当てを解除される。プログラムが実行から退避するならば、このプログラムに割り当てられた論理タイルは他のプログラムに再割り当てられる。新たなプログラムが起動されたならば、その論理タイルは他のプログラムから取り外されて当該新たなプログラムに割り当てられる。
【００５１】
次の動作が支持される。
【００５２】
１．同じ数の論理タイルをプログラムに対して再度割り当てること
２．さらなる論理タイルをプログラムに対して割り当てること
３．論理タイルをプログラムに対する割り当てから解除すること
４．プログラムの退避、および
５．新たなプログラムの起動
例えば他のプログラムが退避するかあるいは新たなプログラムが起動されたときには、プログラムは同じ数の論理タイルが再度割り当てられる。この場合、論理タイルルックアップテーブル４３０はプログラムに関する新たな第１の論理タイルによって更新される。物理アドレスルックアップテーブル４５０は、物理タイルアドレスを古い論理タイルアドレス／位置から新たな論理タイルアドレスへ移動することによって更新される。タグＲＡＭ４７０はまた、タグを古い論理タイルアドレスから新たな論理タイルアドレスへ移動することによって更新される。
【００５３】
プログラムは、例えば論理タイルが利用可能となったとき及び／またはプログラムのキャッシュ利用が増大したときに、さらなる論理タイルが割り当てられる。この場合、論理タイルルックィアップテーブル４３０はプログラムに関する新たな数の割り当て論理タイル（新たなＬ値）によって更新される。命令ＲＡＭ４６０に現在記憶されているプログラム部分のタグは新たなＬ値によって再度計算され、タグＲＡＭ３７０内の適当な論理タイルアドレスに記憶される。新たに割り当てられた論理タイルに関する有効ビットは、これらの論理タイルに関して有効なビットがないことを示すために、”０”に設定される。
【００５４】
プログラムは、例えば新たなプログラムが起動されたときに、いくつかの論理タイルが割り当て解消される。この場合、論理タイルルックアップテーブル４３０は、プログラムに関する新たな数の割り当て論理タイル（新たなＬ値）によって更新される。命令ＲＡＭ４６０に現在記憶されているプログラム部分のタグは、新たなＬ値によって再度計算される。現在割り当てられた論理タイルに関するタグはタグＲＡＭ４７０内の適当な論理タイルアドレスに記憶される。割り当てが解消された論理タイルに関するタグは廃棄される。
【００５５】
プログラムは、プログラムの実行が完了したときに退避される。プログラムに割り当てられた全ての論理タイルは再要求（reclaim）されて他のプログラムに割り当てられる。論理タイルルックアップテーブル４３０はプログラムに関して０が割り当てられた論理タイル（Ｌ＝０）によって更新される。
【００５６】
新たなプログラムが起動されて１つまたはそれ以上の論理タイルが割り当てられる。論理タイルルックアップテーブル４３０は第１の論理タイルと新たなプログラムに割り当てられた論理タイルの数によって更新される。新たに割り当てられた論理タイルに関する有効ビットは”０”に設定される。
【００５７】
上記動作の任意の組み合わせが任意の時点において実行される。例えば、プログラムの退避は残りのプログラムに関する論理タイルの割り当て及び／又は再割り当てを意味する。また、新たなプログラムの起動は、他のプログラムに関する論理タイルの割り当て解除及び／又は再割り当てを意味する。一例として、論理タイルはまず図５に示されるプログラムに対して割り当てられる。次にプログラム２は実行から退避し、このプログラムに割り当てられた８個の論理タイルが他のプログラムに対して再割り当てられる。例えば、プログラム０は、論理タイル０〜７が割り当てられ、プログラム１は論理タイル８〜１１が割り当てられ、プログラム３は論理タイル１２〜１７が割り当てられる。この例において、プログラム０は６つのさらなる論理タイルが割り当てられ、プログラム１は論理タイルが再割り当てられ、プログラム３は２つのさらなる論理タイルが割り当てられる。ルックアップテーブル４３０及び４５０とタグＲＡＭ４７０は上記したようにこれらのプログラムに関して更新される。
【００５８】
明確化のために、論理タイル及び物理タイルを用いた命令キャッシュ２２０の特定の実施形態について上述された。他の実施形態においては、論理タイルが使用されず、プログラムは物理タイルが割り当てられてそれらの割り当てられた物理タイルに直接マッピングされる。ルックアップテーブルは各プログラムに関してどの物理タイルが割り当てられるのかを識別するために用いられる。
【００５９】
タイル化キャッシュはタイルアーキテクチャにより実装されるキャッシュである。概して、タイル化キャッシュは任意の数のタイルを含み、同じサイズまたは異なるサイズを有する。プログラムは論理タイルまたは物理タイルが割り当てられ、直接マッピングあるいはN-wayセット連想スキームを用いて割り当てられたタイルにマッピングされる。タグＲＡＭは論理タイルアドレスまたは物理タイルアドレスによってインデクス化されたタグを記憶する。概して、タイルキャッシュは種々の方法により実装される。タイル化キャッシュに関する種々のユニットの動作は、タイル化キャッシュの設計によってあるいは合致して決定される。
【００６０】
タイル化キャッシュは、種々のタイプのデータを記憶するのに使用される。図２に示す実施形態において、命令キャッシュ２２０及び定数バッファ２１８はそれぞれタイル化キャッシュにより実装される。１つまたはそれ以上のタイル化キャッシュはまた、例えば画素、テクスチャマップなどの種々のタイプのデータを記憶するために、キャッシュメモリシステム１５０において用いられる。
【００６１】
タイル化キャッシュは、キャッシュを共有するプログラム間の廃棄（trashing）の回避、タグ比較に関する低い電力消費、より小さな集積回路（ＩＣ）領域などの利点を提供する。
【００６２】
ここに記述されたキャッシュ技術は、ワイヤレス通信、計算、ネットワーク化、個人用電子機器などに関して用いられる。ワイヤレス通信に関する当該技術の例示的使用について以下に述べる。
【００６３】
図９は、ワイヤレス通信システムにおけるワイヤレス装置９００の実施形態のブロック図を示している。ワイヤレス装置９００は携帯電話、端末、ハンドセット、パーソナルデジタルアシスタント（ＰＤＡ）あるいは他の装置である。ワイヤレス通信システムは符号分割多元接続（ＣＤＭＡ）を用いたシステム、移動体通信に関するグローバルシステム（ＧＳＭ）を用いたシステム、あるいは他のシステムである。
【００６４】
ワイヤレス装置９００は、受信経路及び送信経路を介して双方向通信の提供が可能である。受信経路に関して、基地局から送信された信号はアンテナ９１２によって受信されて受信器（ＲＣＶＲ）９１４に供給される。受信器９１４は受信信号を調整かつデジタル化した後、さらなる処理のためにサンプルをデジタル部９２０に供給する。送信経路に関して、送信器（ＴＭＴＲ）９１６は送信すべきデータをデジタル部９２０から受け取って当該データを処理かつ調整し、変調された信号を生成する。この信号はアンテナ９１２を介して基地局に送信される。
【００６５】
デジタル部９２０は例えばモデムプロセッサ９２２、ビデオプロセッサ９２４、アプリケーションプロセッサ９２６、ディスプレイプロセッサ９２８、コントローラ／プロセッサ９３０、グラフィックスプロセッサ９４０、そして外部バスインタフェース（ＥＢＩ）９６０などの種々の処理及びインタフェースユニットを含む。モデムプロセッサ９２２は、例えば符号化、変調、復調及び復号化などのデータ送信及び受信のための処理を実行する。ビデオプロセッサ９２４は、カムコーダ、ビデオ再生プレイバック、ビデオコンファレンスなどのビデオアプリケーションに関するビデオコンテンツ（例えば静止画、動画、動テキスト）に関する処理を実行する。アプリケーションプロセッサ９２６は、マルチウエイ呼、ウエブブラウジング、メディアプレイヤ、ユーザインタフェースなどの種々のアプリケーションに関する処理を実行する。ディスプレイプロセッサ９２８はディスプレイユニット９８０に関するビデオ、グラフィックス、テキストの再生を行うために処理を実行する。コントローラ／プロセッサ９３０はデジタル部９２０内の種々の処理及びインタフェースユニットの動作を制御する。
【００６６】
グラフィックスプロセッサ９４０は、グラフィックスアプリケーションに関する処理を実行するものであり、上記したように実装される。例えば、グラフィックスプロセッサ９４０は、図２及び図４におけるスレッドスケジューラ２１０及び命令キャッシュ２２０を含む。キャッシュメモリシステム９５０はグラフィックスプロセッサ９４０に関する命令及び／又はデータを記憶する。ＥＢＩ９６０はデジタル部９２０とメインメモリ９７０間のデータの転送を確立する。
【００６７】
デジタル部９２０は、１つまたはそれ以上のデジタルシグナルプロセッサ（ＤＳＰ）、マイクロプロセッサ、減少された命令セットのコンピュータ（ＲＩＳＣ）などによって実装される。デジタル部９２０は１つまたはそれ以上の特定用途集積回路（ＡＳＩＣ）あるいは他のタイプの集積回路（ＩＣ）上に形成される。
【００６８】
ここに記述されたキャッシュ技術は、種々のハードウエアユニットにおいて実装される。例えば、キャッシュはＡＳＩＣ、デジタル信号処理装置（ＤＳＰＤ）、プログラマブルロジックデバイス（ＰＬＤ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、プロセッサ、コントローラ、マイクロコントローラ、マイクロプロセッサ、他の電子ユニットにおいて実装される。
【００６９】
キャッシュ技術の一部分はファームウエア及び／又はソフトウェアにおいて実装される。例えば、タイル化キャッシュの管理及び制御はここに記述された機能を実行するファームウエア及び／又はソフトウェア（例えば手順、機能など）によって実装される。ファームウエア及び／又はソフトウェアコードはメモリ（例えば図９のメモリ９７０）内に記憶されてプロセッサ（例えばプロセッサ９３０）によって実行される。メモリはプロセッサ内部あるいはプロセッサ外部において実現される。
【００７０】
開示された実施形態の前述した説明は、本発明を当業者が製造あるいは使用可能とするために与えられた。当業者ならばこれらの実施形態に対する種々の変形例を容易に考えることができる。ここに規定された一般的な原理は本発明の精神すなわち権利範囲から逸脱することなしに他の実施形態に適用可能である。すなわち、本発明は、ここに記述された実施形態に限定されるべきでなく、ここに開示された原理と新規な特長に合致した広い権利範囲を与えられるべきである。
【図１】
2009545080.tif 000003
【図２】
2009545080.tif 000004
【図３】
2009545080.tif 000005
【図４】
2009545080.tif 000006
【図５】
2009545080.tif 000007
【図６】
2009545080.tif 000008
【図７】
2009545080.tif 000009
【図８】
2009545080.tif 000010
【図９】
2009545080.tif 000011
【国際調査報告】
2009545080.tif 000012
2009545080.tif 000013