(57)【要約】一つの実施形態では、ある方法が提供される。この実施形態の該方法は機械実行可能命令のシーケンスのスケジューリングおよびスケジューリングされた機械実行可能命令のシーケンスに基づくデータ配置の作成を提供する。
2007517324.tif 000002
【特許請求の範囲】
【請求項１】
機械実行可能命令のシーケンスをスケジューリングし、
スケジューリングされた機械実行可能命令のシーケンスに基づいてデータ配置を作成する、
ことを含むことを特徴とする方法。
【請求項２】
前記データ配置が、前記スケジューリングされた機械実行可能命令のシーケンスに基づく色付けされた衝突グラフに従って作成されることを特徴とする、請求項１記載の方法。
【請求項３】
前記色付けされた衝突グラフが：
それぞれが前記機械実行可能命令の一つまたは複数によってアクセスされる一意的なデータ要素に対応し、該それぞれがあるハードウェア資源を表す色を割り当てられる複数のノードと、
もしあればそれぞれが潜在的なハードウェア資源衝突を表すある個数の辺、
とを有することを特徴とする、請求項２記載の方法。
【請求項４】
前記ハードウェア資源がキャッシュメモリ中のデータバンクであることを特徴とする、請求項３記載の方法。
【請求項５】
前記ハードウェア資源衝突が、前記一つまたは複数の機械実行可能命令の複数が同じ実行サイクルにおいて単数のデータバンクにアクセスすることを含むことを特徴とする、請求項４記載の方法。
【請求項６】
同じ色を割り当てられたノードの一対をつなぐ辺のそれぞれがハードウェア資源衝突を表すことを特徴とする請求項４記載の方法。
【請求項７】
複数のノードおよびある個数の辺を有する衝突グラフを作成し、各ノードは少なくとも一つの機械実行可能命令によってアクセスされるデータ要素を表し、各辺はもしあれば前記複数のノードのうちの一対をつなぎ、潜在的なハードウェア資源衝突を表し、
前記複数のノードのそれぞれに色を割り当てることによって前記衝突グラフに色を付けて色付けされた衝突グラフを生成し、各色は一つのハードウェア資源を表し、
各データ要素を一つのメモリ位置にマッピングすることによってデータ配置を作成し、該メモリ位置は対応する一つのハードウェア資源にマッピングされる、
ことを含むことを特徴とする方法。
【請求項８】
請求項７記載の方法であって、前記複数のノードのそれぞれに色を割り当てることが、前記複数のノードのそれぞれの所与のノードについて、対応色セットから色を割り当てることであり、該対応色セットとは複数の色をもつ共同色セットから少なくとも一つの色を有するものであり、前記少なくとも一つの色は前記所与のノードに隣接する一つまたは複数のノードに対応する一つまたは複数の他の色セットに含まれていないものであることを特徴とする方法。
【請求項９】
請求項８記載の方法であって、前記複数のノードのそれぞれの所与のノードについて、前記対応色セットから色を割り当てることが：
前記所与のノードを第一のノードとして指定し、該第一のノードは色付けされていないノードであり、第一の対応色セットに対応しており、
前記第一の対応色セットが空でなければ、前記第一の対応色セットからの第一の色を前記第一のノードに割り当て、
もし一つまたは複数の第二のノードがあり、該一つまたは複数の第二のノードが色付けされておらず、前記第一のノードに隣接しており、一つまたは複数の第二の対応色セットに対応していれば、該一つまたは複数の第二の対応色セットのそれぞれから前記第一の色を除去する、
ことを含むことを特徴とする方法。
【請求項１０】
前記第一の対応色セットが空であれば前記共同色セットからの複数の色の一つを選択することを特徴とする、請求項９記載の方法。
【請求項１１】
前記複数の色のうちの選択された色が重みが最小の衝突色であることを特徴とする、請求項１０記載の方法。
【請求項１２】
前記第一の色がメモリ使用を最小化する色であることを特徴とする、請求項９記載の方法。
【請求項１３】
メモリ使用を最小化する色とはブロックサイズで割りきれないデータサイズに対応している色であることを特徴とする、請求項１２記載の方法。
【請求項１４】
前記複数のノードのそれぞれに優先度を割り当てることをさらに含むことを特徴とする、請求項７記載の方法。
【請求項１５】
請求項１４記載の方法であって、前記複数のノードのそれぞれに優先度を割り当てることが、前記複数のノードの所与のノードについて：
前記所与のノードにつながれた前記一つまたは複数の辺のそれぞれについて重みを決定し、
各ノードに対して、該ノードにつながれた該ノードの一つまたは複数の辺の最大の重みに対応する優先度を割り当て、
前記複数のノードを順位付けする、
ことを含むことを特徴とする方法。
【請求項１６】
請求項１５記載の方法であって、前記ノードにつながれた前記一つまたは複数の辺のそれぞれの所与のものに対する重みを決定することが、該所与の辺によって表されるハードウェア資源衝突に関連するパフォーマンス上のペナルティに基づいて重みを決定することであることを特徴とする方法。
【請求項１７】
請求項１４記載の方法であって、前記複数のノードのそれぞれに色を割り当てることが、前記ノードのそれぞれに割り当てられた対応する優先度の順に前記複数のノードのそれぞれに色を割り当てることを含むことを特徴とする方法。
【請求項１８】
請求項１７記載の方法であって、前記ハードウェア資源がデータバンクであり、前記ハードウェア資源衝突が前記少なくとも一つの機械実行可能命令の複数が同じ実行サイクルにおいて単数のデータバンクにアクセスすることを含むことを特徴とする、請求項１７記載の方法。
【請求項１９】
複数のノードおよびある個数の辺を有する衝突グラフを作成し、各ノードは少なくとも一つの機械実行可能命令によってアクセスされるデータ要素を表し、各辺はもしあれば前記複数のノードのうちの一対をつなぎ、潜在的なハードウェア資源衝突を表し、
前記複数のノードのそれぞれに色を割り当てることによって前記衝突グラフに色を付けて色付けされた衝突グラフを生成し、各色は一つのハードウェア資源を表し、
各データ要素を一つのメモリ位置にマッピングすることによってデータ配置を作成し、該メモリ位置は対応する一つのハードウェア資源にマッピングされる、
ことのできる回路、
を有することを特徴とする装置。
【請求項２０】
請求項１９記載の装置であって、前記回路がさらに対応色セットから色を割り当てることができ、該対応色セットとは複数の色をもつ共同色セットから少なくとも一つの色を有するものであり、前記少なくとも一つの色は所与のノードに隣接する一つまたは複数のノードに対応する一つまたは複数の他の色セットに含まれていないものであることを特徴とする装置。
【請求項２１】
請求項２０記載の装置であって、前記複数のノードのそれぞれの所与のノードについて、前記回路が：
前記所与のノードを第一のノードとして指定し、該第一のノードは色付けされていないノードであり、第一の対応色セットに対応しており、
前記第一の対応色セットが空でなければ、前記第一の対応色セットからの第一の色を前記第一のノードに割り当て、
もし一つまたは複数の第二のノードがあり、該一つまたは複数の第二のノードが色付けされておらず、前記第一のノードに隣接しており、一つまたは複数の第二の対応色セットに対応していれば、該一つまたは複数の第二の対応色セットのそれぞれから前記第一の色を除去する、
ことができることを特徴とする装置。
【請求項２２】
前記回路がさらに、前記複数のノードのそれぞれに優先度を割り当てることができることを特徴とする、請求項１９記載の装置。
【請求項２３】
一つまたは複数のメモリ位置にある複数のデータ要素にアクセスする機械実行可能命令のシーケンスを有するメモリと、
複数のデータバンクを有するL2（レベル２）キャッシュであって、前記一つまたは複数のメモリ位置が前記複数のデータバンクのうちの一つにマッピングされるようなL2キャッシュと、
回路であって：
複数のノードおよびある個数の辺を有する衝突グラフを作成し、各ノードは少なくとも一つの機械実行可能命令によってアクセスされるデータ要素を表し、各辺はもしあれば前記複数のノードのうちの一対をつなぎ、潜在的なデータバンク衝突を表し、
前記複数のノードのそれぞれに色を割り当てることによって前記衝突グラフに色を付けて色付けされた衝突グラフを生成し、各色は一つのデータバンクを表し、
各データ要素を一つのメモリ位置にマッピングすることによってデータ配置を作成し、該メモリ位置は対応する一つのデータバンクにマッピングされる、
ことのできる回路、
とを有することを特徴とするシステム。
【請求項２４】
請求項２３記載のシステムであって、前記回路がさらに対応色セットから色を割り当てることができ、該対応色セットとは複数の色をもつ共同色セットから少なくとも一つの色を有するものであり、前記少なくとも一つの色は所与のノードに隣接する一つまたは複数のノードに対応する一つまたは複数の他の色セットに含まれていないものであることを特徴とするシステム。
【請求項２５】
請求項２４記載のシステムであって、前記複数のノードのそれぞれの所与のノードについて、前記回路がさらに：
前記所与のノードを第一のノードとして指定し、該第一のノードは色付けされていないノードであり、第一の対応色セットに対応しており、
前記第一の対応色セットが空でなければ、前記第一の対応色セットからの第一の色を前記第一のノードに割り当て、
もし一つまたは複数の第二のノードがあり、該一つまたは複数の第二のノードが色付けされておらず、前記第一のノードに隣接しており、一つまたは複数の第二の対応色セットに対応していれば、該一つまたは複数の第二の対応色セットのそれぞれから前記第一の色を除去する、
ことができることを特徴とするシステム。
【請求項２６】
前記回路がさらに前記複数のノードのそれぞれに優先度を割り当てることができることを特徴とする、請求項２４記載のシステム。
【請求項２７】
機械可読媒体であって、機械によって実行されたときに該機械が下記のこと、すなわち：
複数のノードおよびある個数の辺を有する衝突グラフを作成し、各ノードは少なくとも一つの機械実行可能命令によってアクセスされるデータ要素を表し、各辺はもしあれば前記複数のノードのうちの一対をつなぎ、潜在的なハードウェア資源衝突を表し、
前記複数のノードのそれぞれに色を割り当てることによって前記衝突グラフに色を付けて色付けされた衝突グラフを生成し、各色は一つのハードウェア資源を表し、
各データ要素を一つのメモリ位置にマッピングすることによってデータ配置を作成し、該メモリ位置は対応する一つのハードウェア資源にマッピングされる、
ことを実行するという結果を生じる命令のシーケンスを表すデータが保存されていることを特徴とする機械可読媒体。
【請求項２８】
請求項２７記載の機械可読媒体であって、機械によって実行されたときに該機械が複数のノードのそれぞれに色を割り当てるという結果を生じる前記命令のシーケンスが、前記複数のノードのそれぞれの所与のノードについて、対応色セットから色を割り当てるという結果をさらに生じるものであり、該対応色セットとは複数の色をもつ共同色セットから少なくとも一つの色を有するものであり、前記少なくとも一つの色は前記所与のノードに隣接する一つまたは複数のノードに対応する一つまたは複数の他の色セットに含まれていないものであることを特徴とする機械可読媒体。
【請求項２９】
請求項２７記載の機械可読媒体であって、機械によって実行されたときに該機械が前記対応色セットからの色を割り当てるという結果を生じる前記命令のシーケンスがさらに、前記複数のノードのそれぞれの所与のノードについて、前記機械が：
前記所与のノードを第一のノードとして指定し、該第一のノードは色付けされていないノードであり、第一の対応色セットに対応しており、
前記第一の対応色セットが空でなければ、前記第一の対応色セットからの第一の色を前記第一のノードに割り当て、
もし一つまたは複数の第二のノードがあり、該一つまたは複数の第二のノードが色付けされておらず、前記第一のノードに隣接しており、一つまたは複数の第二の対応色セットに対応していれば、該一つまたは複数の第二の対応色セットのそれぞれから前記第一の色を除去する、
という結果を生じることを特徴とする機械可読媒体。
【請求項３０】
前記回路がさらに前記複数のノードのそれぞれに優先度を割り当てることができることを特徴とする、請求項２７記載の機械可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、ハードウェア資源衝突を軽減するためのデータ配置機構に関する。
【背景技術】
【０００２】
コンピュータシステムにおいて、複数のプロセッサがある組み合わせのメモリ位置に時間的に近接して同じ実行サイクル内または互いに数実行サイクル以内にアクセスすることは、たとえばパフォーマンス上のペナルティを生じうる。パフォーマンス上のペナルティとは、ある条件の組のもとでのコンピュータシステムの動作の結果生じうる、典型的には不都合な結果のことをいう。パフォーマンス上のペナルティは、たとえば、メモリアクセスの遅延でありうる。メモリアクセスの遅延はたとえばハードウェア資源衝突のために生じうる。これは、複数のメモリ位置が、同時には一つのデータ要求しか処理できない、キャッシュメモリ中のデータバンクのような同じハードウェア資源を要求するようなものである。
【０００３】
たとえば本出願の被譲り受け者から市販されているインテル（登録商標）アイテニアム（登録商標）２プロセッサでは、レベル２キャッシュ・データ・アレイは１６のバンクを有し、各バンクは１６バイトのデータを格納する。さらに、メモリ位置からデータバンクへのブロック巡回マッピングがあることもある。たとえばインテル（登録商標）アイテニアム（登録商標）２プロセッサにおけるメモリ・サブシステムは、ある実行サイクルの間にデータバンクへの一つの要求しか処理できないかもしれないので、たとえば同じ実行サイクル中に発された二つの読み込みまたは二つの保存が同じデータバンクにマッピングされる複数のメモリ位置を参照していると、ハードウェア資源衝突につながることがあり、メモリアクセスの遅延を引き起こすことがある。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
キャッシュ・データバンク衝突のようなハードウェア資源衝突を軽減または解消するための既存の機構は、データ配置についての情報を使って同じハードウェア資源にマッピングされる、あるいはマッピングされそうなデータを判別し、そのようなデータに衝突しないサイクルにおいてアクセスする命令をスケジューリングする。データ配置機構とは、プログラム命令によってアクセスされるデータをメモリ位置にマッピングする方法のことである。データ配置は静的になされることもある。その場合はデータはコンパイルまたはリンク時にメモリ位置にマッピングされる。あるいはデータ配置は動的になされることもある。その場合はデータはプログラム実行の際にメモリ位置にマッピングされる。既存の機構は、コンパイラがプログラム属性によって許容される限り早いうちにメモリアクセス命令をスケジューリングする能力を制限している。さらに、リンク時に割り当てられるデータなど、命令スケジューリングののちに割り当てられるデータへのアクセスから生じうるハードウェア資源衝突は解消しない。
【０００５】
本発明の実施形態は、限定ではなく例として付属の図面に示されている。図面において同様の参照符号は同様の要素を指す。
【発明を実施するための最良の形態】
【０００６】
本発明の実施形態は、以下に述べられるさまざまな動作を含む。本発明の実施形態に関連する動作はハードウェア要素によって実行されてもよいし、あるいは機械実行可能命令において具現されて、該機械実行可能命令が実行されたときに該機械実行可能命令をプログラムされた汎用または専用プロセッサまたは回路が前記動作を実行する結果を生じるのでもよい。
【０００７】
本発明の実施形態は、たとえば、コンピュータ、コンピュータ網またはその他の電子機器のような一つまたは複数の機械によって実行されたときに該一つまたは複数の機械が本発明の実施形態に基づく動作を実行する結果を生じる機械実行可能命令が保存された一つまたは複数の機械可読媒体を含みうるコンピュータプログラムプロダクトとして提供されてもよい。機械可読媒体とは、これに限定されるものではないが、フロッピー（登録商標）ディスケット、光ディスク、CD-ROM（Compact  Disc‐Read  Only  Memory［コンパクトディスクを利用した読み出し専用メモリ］）および光磁気ディスク、ROM（Read  Only  Memory［読み出し専用メモリ］）、RAM（Random  Access  Memory［ランダムアクセスメモリ］）、EPROM（Erasable  Programmable  Read  Only  Memory［消去可能なプログラム可能読み出し専用メモリ］）、EEPROM（Electrically  Erasable  Programmable  Read  Only  Memory［電気的に消去可能なプログラム可能読み出し専用メモリ］）、磁気または光カード、フラッシュメモリ、または機械実行可能命令を保存するために好適なその他の種類のメディア／機械可読媒体を含みうる。
【０００８】
さらに、本発明の実施形態は、コンピュータプログラムプロダクトとしてダウンロードされるのでもよい。ここで、プログラムはリモートコンピュータ（たとえばサーバー）から要求側コンピュータ（たとえばクライアント）に、搬送波またはその他の伝搬媒体に具現された、および／またはそれらによって変調された一つまたは複数のデータ信号によって、通信リンク（たとえばモデムおよび／またはネットワーク接続）を経由して転送されうるものである。したがって、ここでの用法では、前記機械可読媒体は、必須ではないが、そのような搬送波であってもよい。
【０００９】
以下に述べられる例はあくまでも解説のためのものであり、決して本発明の実施形態を限定することを意図したものではない。よって、例が詳細に述べられるようなところでも、あるいは例のリストが挙げられるようなところでも、それらの例は網羅的であると解釈されるものではなく、本発明の実施形態を記載および／または図解された例に限定するものでもないことは理解しておくべきである。
【００１０】
〈序〉
図１はシステムを示している。システム１００はホストプロセッサ１０２、ホストメモリ１０４、バス１０６およびチップセット１０８を有しうる。ホストプロセッサ１０２はたとえばインテル（登録商標）アイテニアム（登録商標）２プロセッサであってもよい。もちろん、代替的にホストプロセッサ１０２は、たとえば本出願の被譲り受け者以外のソースから製造および／または市販されているマイクロプロセッサのような別の型のマイクロプロセッサであることも、この実施形態から外れることなくできる。
【００１１】
ホストプロセッサ１０２はチップセット１０８に通信可能的に結合されうる。ここでの用法では、第一の構成要素が第二の構成要素に「通信可能的に結合」されているとは、第一の構成要素が第二の構成要素と有線の（たとえば銅線の）または無線の（たとえば電波周波数の）手段を経由して通信できることを意味するものとする。チップセット１０８は、ホストプロセッサ１０２、ホストメモリ１０４およびユーザーインターフェースシステム１１４を互いに、そしてバス１０６に結合しうるホスト・ブリッジ／ハブ・システムを有しうる。チップセット１０８はまた、前記ホスト・ブリッジ／バス・システム１０８をバス１０６に結合しうるI/Oブリッジ／ハブ・システム（図示せず）をも含みうる。チップセット１０８は本発明の被譲り受け者から市販されている集積回路チップセットから選択されるもののような集積回路チップ（たとえばグラフィック・メモリおよびI.Oコントローラ・ハブ・チップセット）であってもよい。ただし、代替的にその他の集積回路チップを使用してもよい。ユーザーインターフェースシステム１１４は、人間のユーザーがシステム１００にコマンドを入力したり、システム１００の動作をモニターしたりすることなどを許容する、たとえばキーボード、ポインティングデバイスおよびディスプレイシステムなどを有しうる。
【００１２】
バス１０６は、米国オレゴン州ポートランドのPCI特別利益団体から入手できる周辺コンポーネント相互接続（PCI）ローカルバス規格、修正2.2版、1998年12月18日に準拠するバス（以下、「PCIバス」と称する）であってもよい。代替的に、バス１０６はその代わりに、米国オレゴン州ポートランドの前記PCI特別利益団体から入手できるPCI-X規格、修正1.0a版、2000年7月24日に準拠するバス（以下、「PCI-Xバス」と称する）であってもよい。また、代替的に、バス１０６はその他の種類および構成のバス・システムであってもよい。
【００１３】
システム１００は、ホストプロセッサ１０２のようなプロセッサならびに／または回路１２６のような回路によって実行されることのできる機械実行可能命令１３０、１３２ならびに／またはアクセス、作用および／または操作されることのできるデータを保存するための一つまたは複数のメモリを有しうる。メモリはたとえば、ホストメモリ１０４および回路１２６内のメモリ１２８を含みうる。メモリ１０４、１２８は読み出し専用、大容量記憶および／またはランダムアクセスのコンピュータ可読メモリでありうる。プロセッサ１０２および／または回路１２６によるプログラム命令１３０、１３２の実行ならびに／またはこのデータのアクセス、作用および／または操作は、たとえば、プロセッサ１０２および／または回路１２６がここに記載される動作の一部または全部を実行する結果を生じうる。
【００１４】
ホストプロセッサ１０２、ホストメモリ１０４、バス１０６、チップセット１０８および回路カードスロット１１６は、たとえばシステム・マザーボード１１８のような単一の回路基板に含まれていてもよい。回路カードスロット１１６は、PCIバスコネクタ１２０を有するPCI拡張スロットであってもよい。PCIバスコネクタ１２０は、回路カード１２４に含まれるPCIバスコネクタ１２２と電気的および機械的に対になりうる。回路カードスロット１１６および回路カード１２４は、回路カード１２４が回路カードスロット１１６中に挿入されることを許容するよう構築されうる。回路カード１２４が回路カードスロット１１６に挿入されると、PCIバスコネクタ１２０、１２２が電気的および機械的に相互に結合されうる。PCIバスコネクタ１２０、１２２がそのように相互に結合されると、回路カード１２４中の回路１２６は電気的にバス１０６に結合されうる。
【００１５】
図２は、システム１００の一つまたは複数の構成要素のうちに実装されうる、本発明のある実施形態に基づくシステム実施形態２００を示している。システム２００はコンパイラ２０２、キャッシュメモリ２０４、メモリ２０６およびプロセッサ２０８を含みうる。
【００１６】
コンパイラ２０２はソースコードまたはバイトコード２１８を、ホストプロセッサ１０２のようなプロセッサ２０８によって実行されうる機械実行可能命令２２０に変換しうる機能をいう。機械実行可能命令２２０はメモリ１０４のようなメモリ中に存在してもよく、たとえば機械実行可能命令１３２であってもよい。ある実施形態では、コンパイラ２０２は、ホストメモリ１０４上で機械実行可能命令１３２のような機械実行可能命令で具現されていてもよい機械実行可能プログラムを有しうる。本発明の諸実施形態では、コンパイラ２０２は色付けされた衝突グラフ２１２を生成してもよい。コンパイラ２０２は、機械実行可能命令２２０によってアクセスされるプログラムデータ２１６をマッピングすることによって、データをメモリ２０６中の複数のメモリ位置２１４に、色付けされた衝突グラフに従って配置しうる。プログラムの実行時には、プロセッサ２０８は、メモリ２０６中のメモリ位置２１４をキャッシュメモリ２０４中のデータバンク２１０に割り当てることを、メモリ位置‐データバンク・マッピングに従って行いうる。
【００１７】
コンパイラ２０２はジャストインタイム・コンパイラ（以下、「JITコンパイラ」）であってもよい。JITコンパイラというのは、動的にバイトコードをオブジェクトコードに変換しうる機械実行可能プログラムのことをいう。ここで、ソースコードはまずバイトコードに変換されていることができる。JITコンパイラは、機械実行可能プログラムが実行されている際に、命令長のようなコンピュータプラットフォームの相違が認識され、受け入れられることを（静的にではなく動的に）可能にする。バイトコードが、いかなるプラットフォームにも直接送られ、そのプラットフォーム上で実行されることができる、プラットフォームに依存しないコードでありうるからである。
【００１８】
たとえばJava（登録商標）プログラミング言語および環境を考える。これはJames  Gosling,  Bill  Joy,  and  Guy  Steele,  “The  Java（登録商標）  Language  Specification”,  Addison-Wesley,  1991に記載されており、サン・マイクロシステムズ社から市販されている。Java（登録商標）プログラミング言語および環境においては、ソースコードプログラムはJava（登録商標）プログラミング言語で書かれうる（以下「Java（登録商標）プログラム」）。Java（登録商標）プログラムは、Java（登録商標）仮想マシンを有する機械上で実行されうる。Java（登録商標）コンパイラのようなコンパイラがJava（登録商標）プログラムをバイトコードに翻訳することができ、Java（登録商標）仮想マシンがJITコンパイラを用いてバイトコードを機械実行可能命令に変換することができる。代替的に、コンパイラ２０２は静的なコンパイラでもよい。静的なコンパイラというのは、ソースコードを特定のプラットフォームによって理解されうるオブジェクトコードに変換しうる機械実行可能プログラムのことをいう。
【００１９】
キャッシュメモリ２０４は高速メモリのことをいい、たとえば高速RAM（ランダムアクセスメモリ）であってもよい。キャッシュメモリ２０４は、頻繁にアクセスされうるプログラムデータ２１６またはプログラミング命令（たとえば機械実行可能命令２２０）のような情報を保存するのに使用されうる。たとえば、キャッシュメモリ２０４は、プログラム実行中の時間の９０％アクセスされるプログラミング命令、あるいは機械実行可能プログラムによって繰り返しアクセスされうるプログラムデータ２１６を保存するために使用されうる。
【００２０】
キャッシュメモリ２０４はレベル１（以下「L1」）キャッシュであってもよい。L1キャッシュとは、ホストプロセッサ１０２上に直接位置しているメモリのことでありうる（ホストプロセッサ１０２上のメモリは図示していない）。代替的に、キャッシュメモリ２０４はレベル２（以下「L2」）キャッシュであってもよい。L2キャッシュとは、ホストプロセッサ１０２の外部に位置する、メモリ１０４またはメモリ１２８のようなメモリでありうる。キャッシュメモリ２０４は一つまたは複数のデータバンク２１０を有しうる。「データバンク」とは、キャッシュメモリ中のデータにアクセスするために使用されうるハードウェア資源である。データバンクは一つまたは複数の処理制約を有しうる。たとえば、データバンク２１０はある実行サイクルの間には一つのデータ要求しか処理できないなどである。結果として、実行時に同じデータバンク２１０にマッピングされる複数のメモリ位置２１４にあるプログラムデータ２１６に、複数の機械可読命令が同じ実行サイクルの間にアクセスすると、ハードウェア資源衝突の結果を生じうる。
【００２１】
メモリ２０６は、たとえばホストメモリ１０４またはメモリ１２８のようなメモリでありうる。図２に示した例では、メモリ２０６は、プログラムデータ２１６を保存することができ、該プログラムデータ２１６は、プロセッサ２０８による高速のより速いアクセスのためにキャッシュメモリ２０４の一つまたは複数のデータバンク２１０にコピーされうる。
【００２２】
図１１は、第一の実施形態に基づく方法を示している。追加的に図２〜図８を参照すると、コンパイラ２０２（図２）は、プロセッサ２０８による実行のために、メモリ２０６（図２）のようなメモリから読み込まれた機械実行可能命令３２８、３３０、３３２、３３４、３３６、３３８のシーケンス（図３および図２の２２０）を、ブロック１１００にてスケジューリングしうる。機械可読命令２２０のスケジューリングは、プログラム実行の間に、該機械実行可能命令２２０がプロセッサ２０８に送られる順番を決定しうる。本発明の諸実施形態においては、スケジューリングされた機械実行可能命令２２０は、該機械実行可能命令２２０がメインメモリ２０６に保存されている順番に処理回路２１２に送られうる。
【００２３】
ブロック１１０２のデータ配置段階の間に、コンパイラ２０２は、機械実行可能命令３２８、３３０、３３２、３３４、３３６、３３８のスケジューリングされたシーケンス（図３）に基づいてデータ配置８００（図８）を作成しうる。ある実施形態では、データ配置８００はデータ要素３５２、３５４、３５６、３５８（図３）の配置でありうる。ここで、データ要素３５２、３５４、３５６、３５８はプログラムデータ２１６（図２）内のデータでありうる。データ配置８００は、色付けされた衝突グラフ７００（図７）に基づいて作成されうる。この色付けされた衝突グラフ７００は、機械実行可能命令３２８、３３０、３３２、３３４、３３６、３３８のスケジューリングされたシーケンスに基づくものである。データ配置８００は、プログラム実行の間のハードウェア資源衝突を軽減または解消するような、データ要素３５２、３５４、３５６、３５８のメモリ位置２１４へのマッピングに対応しうる。
【００２４】
図１２は、前記第一の実施形態に基づくもう一つの方法を示している。ここでも追加的に図２〜図８を参照すると、ブロック１２００においてコンパイラ２０２（図２）は複数のノード３０２、３０４、３０６、３０８およびいくつかの辺３１０、３１２、３１４を有する衝突グラフ３００（図３）を作成しうる。ここで、辺の数は０以上でありうる。各ノード３０２、３０４、３０６、３０８は、少なくとも一つの機械実行可能命令によってアクセスされうるデータ要素３５２、３５４、３５６、３５８を表しうる。各辺３１０、３１２、３１４はもしあるとすれば、前記複数のノード３０２、３０４、３０６、３０８のうちの一対をつなぎうるもので、潜在的なハードウェア資源衝突を表しうる。ブロック１２０２において、コンパイラ２０２（図２）は、前記複数のノード３０２、３０４、３０６、３０８のそれぞれに色C1（４１２）、C2（４１４）、C3（４１６）を割り当てることによって、衝突グラフに色を付けて色付けされた衝突グラフ７００（図７）を生成しうる。ここで、各色が一つのハードウェア資源を表しうる。ブロック１２０４において、コンパイラは、各データ要素を一つのメモリ位置２１４にマッピングすることによって、データ配置８００（図８）を作成しうる。ここで、各メモリ位置２１４は対応する一つのハードウェア資源にマッピングされうる。
【００２５】
本発明の実施形態では、衝突グラフ３００において辺３１０、３１２、３１４（図３）によって表されうる潜在的なハードウェア資源衝突は、辺によってつながれている一対のノードが同じ色を割り当てられている場合にハードウェア資源衝突の結果を生じうる。このようにして、色付けされた衝突グラフ７００（図７）を使用して、その後のハードウェア資源衝突を避けるようにハードウェア資源をデータ要素３５２、３５４、３５６、３５８（図３）に割り当てうる。ある実施形態では、ハードウェア資源へのデータ要素３５２、３５４、３５６、３５８の割り当ては、ノード３０２、３０４、３０６、３０８に対応するデータ要素DATA1（３５２）、DATA2（３５４）、DATA3（３５６）、DATA4（３５８）をデータバンク２１０にマッピングされるメモリ位置２１４に割り当てることによって行われうる。
【００２６】
「ハードウェア資源衝突」とは、データバンク２１０のようなハードウェア資源の制約のために、該ハードウェア資源にアクセスすることから結果として生じうる衝突を意味する。「衝突グラフ」とは、データ要素３５２、３５４、３５６、３５８のようなデータ要素の間の潜在的な衝突の描写である。ある実施形態では、各データ要素３５２、３５４、３５６、３５８は対応するノード３０２、３０４、３０６、３０８によって表されることができ、前記複数のノード３０２、３０４、３０６、３０８の一対のノードの間の潜在的な衝突は、辺３１０、３１２、３１４によって表されうる。色付けされた衝突グラフ８００における前記複数のノード３０２、３０４、３０６、３０８はさらに色を割り当てられて、色付けされた衝突グラフ７００を生じる。「色付けされた衝突グラフ」とは、もしあれば衝突を描写しうるもので、辺によってつながれている何らかのノード対に同じ色が割り当てられていることによって表されうる。各色は一意的なハードウェア資源に対応しうるので、辺３１０、３１２、３１４によってつながれた前記複数のノード３０２、３０４、３０６、３０８（図３）の一対のノードに同じ色を割り当てることがプログラム実行の間の衝突につながりうるのである。前記複数のノード３０２、３０４、３０６、３０８の各ノードに注意深く色を割り当てることによって、ハードウェア資源衝突が軽減され、あるいは場合によっては解消されることがありうる。
【００２７】
図３を参照すると、コンパイラ２０２は、機械実行可能命令３２８、３３０、３３２、３３４、３３６、３３８のシーケンスによって参照されるデータ要素３５２、３５４、３５６、３５８をメモリ位置２１４（ここで、各メモリ位置２１４はデータバンク２１０のようなハードウェア資源にマッピングされていることができる）に、色付けされた衝突グラフ７００（図７）に従ってマッピングすることによってデータ配置８００（図８）を作成しうる。色付けされた衝突グラフ７００に従って作成されうるデータ配置８００は、データ要素３５２、３５４、３５６、３５８がハードウェア資源に、ハードウェア資源衝突が軽減または解消されうるように割り当てられることを可能にする。コンパイラ２０２はデータ配置段階においてデータ配置８００を作成しうる。
【００２８】
〈衝突グラフ〉
本発明の実施形態では、コンパイラ２０２はメモリ位置‐データバンク・マッピング情報を使って、プログラム実行の間に起こりうるデータバンク衝突を軽減または解消するためにどのデータバンクがどのメモリ位置２１４のために使用されるかを推定しうる。ある実施形態では、コンパイラ２０２は。潜在的なデータバンク衝突を示しうる衝突グラフ３００を生成しうる。データバンク衝突は、データ要素３５２、３５４、３５６、３５８（同じデータバンク２１０にマッピングされるメモリ位置２１４に位置している）に命令３２８、３３０、３３２、３３４、３３６、３３８によって同じ実行サイクル内にアクセスされる結果でありうる。この実施形態では、ノードはデータ要素３５２、３５４、３５６、３５８を表していることができ、一対のノードの間の辺は、該対のノードに対応するデータ要素３５２、３５４、３５６、３５８が同じバンク２１０にマッピングされるメモリ位置２１４に位置しており、命令３２８、３３０、３３２、３３４、３３６、３３８によって同じ実行サイクル３１６、３２０、３２４内にアクセスされる場合のデータバンク衝突を表していることができる。データ要素３５２、３５４、３５６、３５８を表しうるノードは、データ要素３５２、３５４、３５６、３５８に対応するノードでありうる。
【００２９】
図３に示されているように、衝突グラフ３００は複数のノード３０２、３０４、３０６、３０８およびいくつかの辺３１０、３１２、３１４を含みうる。ここで、辺の数は０以上である。もしあれば各辺３１０、３１２、３１４は、前記複数のノード３０２、３０４、３０６、３０８のうちの一対のノードをつなぎうる。たとえば図３に示されるように、EDGE1（３１０）はノード３０２をノード３０４につなぐ。EDGE2（３１２）はノード３０４をノード３０６につなぐ。EDGE3（３１４）はノード３０６をノード３０８につなぐ。
【００３０】
図３では、命令（instruction）I1（３２８）はデータ要素DATA1（３５２）に実行サイクルY1（３１６）においてアクセスしうる。命令I2（３３０）はデータ要素DATA2（３５４）に実行サイクルY1（３１６）においてアクセスしうる。命令I3（３３２）はデータ要素DATA2（３５４）に実行サイクルY10（３２０）においてアクセスしうる。命令I4（３３４）はデータ要素DATA3（３５６）に実行サイクルY10（３２０）においてアクセスしうる。命令I5（３３６）はデータ要素DATA3（３５６）に実行サイクルY20（３２４）においてアクセスしうる。命令I6（３３８）はデータ要素DATA4（３５８）に実行サイクルY20（３２４）においてアクセスしうる。
【００３１】
本発明の実施形態では、一つまたは複数の機械実行可能命令I1（３２８）、I2（３３０）、I3（３３２）、I4（３３４）、I5（３３６）、I6（３３８）によってアクセスされうる各データ要素３５２、３５４、３５６、３５８に対してノード３０２、３０４、３０６、３０８が作成されうる。各ノード３０２、３０４、３０６、３０８が一意的なデータ要素３５２、３５４、３５６、３５８に対応するようにされる。本発明のある実施形態では、辺３１０、３１２、３１４は、ノード３０２、３０４、３０６、３０８の対に対応するデータ要素３５２、３５４、３５６、３５８が命令３２８、３３０、３３２、３３４、３３６、３３８によって同じ実行サイクル３１６、３２０、３２４においてアクセスされる場合に前記ノード３０２、３０４、３０６、３０８の対を結びうるものである。
【００３２】
コンパイラ２０２は、例示的なアルゴリズムを使って衝突グラフを以下のようにして生成しうる：
１．各データ要素のためのノードを作成する。
２．前記複数のノードの各ノード対について、該ノードに対応するデータ要素を同じハードウェア資源にマッピングすることが衝突につながりうる場合に該ノードどうしの間の辺を作成する。これはたとえば次によって達成されうる：
・各データ要素がある一つのノード（上記の１項目１で作成されたもの）に対応しうるとして、各命令が一つまたは複数のデータ要素にアクセスしうるような衝突する命令の対を決定する。ここでの用法では、「衝突する命令」とは同じサイクルにおいて実行される複数の命令をいう。
・各データ要素が前記衝突する命令対の少なくとも一つの命令によってアクセスされうるようなデータ要素に対応するノード間に辺を作成する。
【００３３】
たとえばある実施形態では、下記の例に示されるように、辺は、前記ノード対に対応するデータ要素３４２、３４４、３４６、３４８が命令３２８、３３０、３３２、３３４、３３６、３３８によって同じ実行サイクル３１６、３２０、３２４においてアクセスされる場合に前記複数のノード３０２、３０４、３０６、３０８の対の間に作成されうる。
【００３４】
図３では、衝突グラフ３００は以下のようにして作成されうる：
１．各データ要素についてノードを作成する。
ノード３０２はDATA1（３５２）に割り当てられうる。
ノード３０４はDATA2（３５４）に割り当てられうる。
ノード３０６はDATA3（３５６）に割り当てられうる。
ノード３０８はDATA4（３５８）に割り当てられうる。
２．前記複数のノードのうちの各ノード対について、前記ノード対に対応するデータ要素３４２、３４４、３４６、３４８が命令３２８、３３０、３３２、３３４、３３６、３３８によって同じ実行サイクル３１６、３２０、３２４においてアクセスされる場合に前記複数のノード３０２、３０４、３０６、３０８の対の間に辺が作成されうる。衝突する命令の以下の対について、辺３１０、３１２、３１４は以下のようにして作成されうる：
I1（３２８）およびI2（３３０）はいずれもY1（３１６）において実行されうる：これらの命令は、ノード３０２およびノード３０４に対応するデータ要素DATA1（３５２）およびDATA2（３５４）にアクセスする。よって、辺EDGE1（３１０）がノード３０２およびノード３０４の間に作成されうる。
I3（３３２）およびI4（３３４）はいずれもY10（３２０）において実行されうる：これらの命令は、ノード３０４およびノード３０６に対応するデータ要素DATA2（３５４）およびDATA3（３５６）にアクセスする。よって、辺EDGE2（３１２）がノード３０４およびノード３０６の間に作成されうる。
I5（３３６）およびI6（３３８）はいずれもY20（３２４）において実行されうる：これらの命令は、ノード３０６およびノード３０８に対応するデータ要素DATA3（３５６）およびDATA4（３５８）にアクセスする。よって、辺EDGE3（３１４）がノード３０６およびノード３０８の間に作成されうる。
【００３５】
まとめると、３つの辺３１０、３１２、３１４が衝突グラフ３００において作成されうる。EDGE1（３１０）はノード３０２とノード３０４をつなぎうる。これらのノードに対応するデータ要素DATA1（３５２）とDATA2（３５４）が命令I1（３２８）およびI2（３３０）によって同じ実行サイクルY1（３１６）においてアクセスされるからである。EDGE2（３１２）はノード３０４とノード３０６をつなぎうる。これらのノードに対応するデータ要素DATA2（３５４）とDATA3（３５６）が命令I3（３３２）およびI4（３３４）によって同じ実行サイクルY10（３２０）においてアクセスされるからである。EDGE３１４はノード３０６とノード３０８をつなぎうる。これらのノードに対応するデータ要素DATA3（３５６）とDATA4（３５８）が命令I5（３３６）およびI6（３３８）によって同じ実行サイクルY20（３２４）においてアクセスされるからである。
【００３６】
〈色付けされた衝突グラフ〉
本発明の実施形態では、各色C1（４１２）、C2（４１４）、C3（４１６）は、キャッシュメモリ２０４内のデータバンク２１０のような一つのハードウェア資源に対応しうるものである。データバンクを例として使うと、衝突グラフ３００内の各ノードは該ノードに色を割り当てることによって色を付けられうる。ノードへの色の割り当ては、該ノードによって表されているデータへのハードウェア資源の割り当てを表しうる。二つのノードをつなぐ辺は、パフォーマンス上のペナルティにつながりうる潜在的なハードウェア資源衝突を表しうる。辺によって表されるそのような潜在的なハードウェア資源衝突は、その辺によってつながれたノードに同じ色（つまり同じハードウェア資源）が割り当てられた場合にハードウェア資源衝突という結果を生じうる。本発明の実施形態では、こうしたパフォーマンス上のペナルティを回避するために、隣接ノードに異なる色を付ける努力がなされる。ここでの用法では、「隣接ノード」とは、EDGE1（３１０）、EDGE2（３１２）、EDGE3（３１４）のような何らかの辺によってつながれるノードである。「色付けされたノード」とは色を割り当てられたノードのことで、「色付けされていないノード」とは色を割り当てられていないノードである。
【００３７】
衝突グラフ内の各ノードについて、コンパイラ２０２は、色セット４１０Ａ、４１０Ｂ、４１０Ｃ、４１０Ｄ（図４、ここで各色セットは以下では「対応色セット」と称される）および／または共同色セット４１０のような色セットを作成して維持しうる。各対応色セット４１０Ａ、４１０Ｂ、４１０Ｃ、４１０Ｄは初期には共同色セット４１０からの諸色を有しうる。ここで、共同色セット４１０は複数の色C1（４１２）、C2（４１４）、C3（４１６）を含みうる。図４に示されるように、コンパイラ２０２は現在ノードに対応色セット４１０Ａ、４１０Ｂ、４１０Ｃ、４１０Ｄから、あるいは共同色セット４１０から色を割り当てうる。ノードに色が付けられていくにつれ、対応色セット４１０Ａ、４１０Ｂ、４１０Ｃ、４１０Ｄから色が除去されうる。それにより対応色セット４１０Ａ、４１０Ｂ、４１０Ｃ、４１０Ｄは、共同色セット４１０中の色C1（４１２）、C2（４１４）、C3（４１６）のうちの皆無から共同色セット４１０中の色C1（４１２）、C2（４１４）、C3（４１６）の全部に至るまであらゆる可能性をとることができ、また対応色セット４１０Ａ、４１０Ｂ、４１０Ｃ、４１０Ｄは当該現在ノードの隣接ノードに割り当てられていない色のセットを表すようにできる。結果として、現在ノードが空でないある対応色セット４１０Ａ、４１０Ｂ、４１０Ｃ、４１０Ｄを有している場合、現在ノードは隣接ノードと同じ色になることはない。
【００３８】
図示した実施形態では、各ノードには対応色セット４１０Ａ、４１０Ｂ、４１０Ｃ、４１０Ｄが関連付けられうる。ノード３０２、３０４、３０６、３０８のおのおのは、それぞれ対応色セット４１０Ａ、４１０Ｂ、４１０Ｃ、４１０Ｄからの、あるいは共同色セット４１０からの色C1（４１２）、C2（４１４）、C3（４１６）を割り当てられうる。コンパイラ２０２は、複数のノード３０２、３０４、３０６、３０８のうちの一つを現在ノードとして指定することができ、それに対して対応色セット４１０Ａ、４１０Ｂ、４１０Ｃ、４１０Ｄから、あるいは共同色セット４１０から色C1（４１２）、C2（４１４）、C3（４１６）を割り当てることになる。コンパイラ２０２は、対応色セット４１０Ａ、４１０Ｂ、４１０Ｃ、４１０Ｄから、あるいは共同色セット４１０から第一の色を選択して、それを現在ノードに割り当てることができる。ある実施形態では、コンパイラ２０２は、対応色セット４１０Ａ、４１０Ｂ、４１０Ｃ、４１０Ｄが空でない場合に、対応色セット４１０Ａ、４１０Ｂ、４１０Ｃ、４１０Ｄから色C1（４１２）、C2（４１４）、C3（４１６）を選択しうる。対応色セット４１０Ａ、４１０Ｂ、４１０Ｃ、４１０Ｄが空である場合には、コンパイラ２０２は共同色セット４１０から色を選択しうる。
【００３９】
対応色セット４１０Ａ、４１０Ｂ、４１０Ｃ、４１０Ｄは、各ノード３０２、３０４、３０６、３０８が処理されるにつれて決定されうるが、その際、たとえばコンパイラが各対応色セット４１０Ａ、４１０Ｂ、４１０Ｃ、４１０Ｄを共同色セット４１０からの全色C1（４１２）、C2（４１４）、C3（４１６）を含むよう初期化することができ、そして現在ノードの処理の間に現在ノードに割り当てられた色C1（４１２）、C2（４１４）、C3（４１６）を現在ノードに隣接するすべてのノードの対応色セット４１０Ａ、４１０Ｂ、４１０Ｃ、４１０Ｄから除去しうるようにしてなされる。代替的に、コンパイラ２０２は各ノードについて対応色セット４１０Ａ、４１０Ｂ、４１０Ｃ、４１０Ｄをそのノードの処理の間に決めることもできるが、その際、たとえば、まず現在ノードについての対応色セット４１０Ａ、４１０Ｂ、４１０Ｃ、４１０Ｄを共同色セット４１０からの全色C1（４１２）、C2（４１４）、C3（４１６）を含むよう初期化し、現在ノードの隣接ノードに割り当てられている色C1（４１２）、C2（４１４）、C3（４１６）を前記現在ノードの対応色セット４１０Ａ、４１０Ｂ、４１０Ｃ、４１０Ｄから除去するようにしてなされる。この方法では、各ノードについて色セットを維持することは必要ではないこともありうる――単一の色セットが維持され、現在ノードそれぞれについて再計算されるのでもよいのである。いずれの方法も受け入れられるもので、本発明の実施形態から外れるものではない。
【００４０】
〈色セットからの色の選択〉
本発明の実施形態では、対応色セット４１０Ａ、４１０Ｂ、４１０Ｃ、４１０Ｄが空でない場合、色は対応色セット４１０Ａ、４１０Ｂ、４１０Ｃ、４１０Ｄから任意に、あるいはその色がメモリ使用を最小にするように選択されうる。本発明の実施形態では、色がメモリ使用を最小化するのは、その色がブロックサイズで割ったときに整数にならないデータサイズに対応する場合である。ここでの用法では、「ブロックサイズ」とは、データバンクのような同じハードウェア資源にマッピングされるある連続したメモリブロックの大きさを意味する。ここでの用法では、あるデータサイズに「対応する」色とは、そのデータサイズに等しい合計データサイズをもつ一つまたは複数のデータ要素に割り当てられうる色を意味する。例として、各データ要素が８バイトの場合、データ要素３５２、３５４、３５６、３５８に対応するノード３０２、３０４、３０６、３０８に色が割り当てられるたびに、その色の対応データサイズが８バイト増えうる。ある色に対応するデータサイズがブロックサイズで割ったときに整数になれば、その色を別のデータ要素に割り当てることは、新しいメモリブロックを開始することにつながる。したがって、メモリ使用を最小化するためには、色の割り当ては、すでに一つまたは複数のデータ要素を有するブロック中にデータ要素が置かれうるようになされ、それによりメモリ中でのメモリ位置の使用が最小化される。ブロックサイズで割ったときに整数にならないデータサイズに対応する色を選択することは、メモリ使用を最小化する結果を生じうる。
【００４１】
この概念を説明するため、図１０に注意を向けうる。図１０は、メモリ位置0〜15、16〜31、…、240〜255、256〜271、272〜287、…、496〜511と、インテル（登録商標）アイテニアム（登録商標）２プロセッサのようなデータバンク１００２Ａ、１００２Ｂ、…１００２Ｎとの間のブロック巡回マッピングを説明するものである。メモリ位置0〜15、16〜31、…、240〜255、256〜271、272〜287、…、496〜511は、たとえばメモリ２０６内のメモリ位置２１４でありうる。データバンク１００２Ａ、１００２Ｂ、…１００２Ｎはたとえばキャッシュメモリ２０４内のバンク２１０でありうる。
【００４２】
ブロック巡回マッピングでは、それぞれメモリ位置0〜15、16〜31、…、240〜255、256〜271、272〜287、…、496〜511からなるメモリブロック１００４Ａ、１００４Ｂ、…１００４Ｃ、１００４Ｄ、１００４Ｅ、…１００４Ｎのそれぞれのデータバンク１００２Ａ、１００２Ｂ、…１００２Ｎへのマッピングは、どのデータバンク１００２Ａ、１００２Ｂ、…１００２Ｎも一つまたは複数のメモリブロックデータバンク１００２Ａ、１００２Ｂ、…１００２Ｎからのデータを有するようにされうる。図１０に示した例では、データバンク１００２Ａはメモリブロック１００４Ａ、１００４Ｄなどからのデータを保持しうる。データバンク１００２Ｂはメモリブロック１００４Ｂ、１００４Ｅなどからのデータを保持しうる。そしてデータバンク１００２Ｎはメモリブロック１００４Ｃ、１００４Ｚなどからのデータを保持しうる。（メモリ位置511より先のメモリ位置およびメモリブロック１００４Ｚより先のメモリブロックが存在してもいいが、図示していない。）
コンパイラは共同色セット４１０内の各色C1（４１２）、C2（４１４）、C3（４１６）に対応するデータサイズを維持していることができる。現在ノードについてのメモリ使用を最小化する色を決定するために、コンパイラは現在ノードに割り当てられることのできるすべての色C1（４１２）、C2（４１４）、C3（４１６）のデータサイズを解析しうる。いずれかの色C1（４１２）、C2（４１４）、C3（４１６）がブロックサイズで割ったときに整数にならないデータサイズに対応していたら、その色C1（４１２）、C2（４１４）、C3（４１６）が選択されうる。複数の色C1（４１２）、C2（４１４）、C3（４１６）がブロックサイズで割ったときに整数にならないデータサイズに対応していたら、これらの色C1（４１２）、C2（４１４）、C3（４１６）のいずれでも任意に選択できる。ブロックサイズで割ったときに整数にならないデータサイズに対応する色がない場合には、最小のデータサイズに対応する色が選択されうる。
【００４３】
〈最小重み衝突色の決定〉
隣接ノードに異なる色を付けることが可能でない（すなわち、対応色セット４１０Ａ、４１０Ｂ、４１０Ｃ、４１０Ｄが空である）場合、ある実施形態では、共同色セット４１０から色が任意に選択されうる。別の実施形態では、共同色セット４１０から色が、ハードウェア資源衝突に関連するパフォーマンス上のペナルティを最小にするよう選択されうる。ある実施形態では、衝突グラフ３００における潜在的なデータバンク衝突が辺EDGE1（３１０）、EDGE2（３１２）、EDGE3（３１４）によって描写されうる。そしてそのような潜在的データバンク衝突が実際の衝突につながる場合のそのような衝突のパフォーマンス上のペナルティは、辺EDGE1（３１０）、EDGE2（３１２）、EDGE3（３１４）に割り当てられる重みによって表されうる。たとえば、大きな重みほどパフォーマンスに対して大きな影響をもつ衝突を表すなどである。別の言い方をすれば、辺EDGE1（３１０）、EDGE2（３１２）、EDGE3（３１４）の重みを決定することは、該辺EDGE1（３１０）、EDGE2（３１２）、EDGE3（３１４）によって表されるハードウェア資源衝突に関連するパフォーマンス上のペナルティを決定することでありうる。ある実施形態では、辺EDGE1（３１０）、EDGE2（３１２）、EDGE3（３１４）は、同じ実行サイクルの間にあるデータバンク中のデータにアクセスすることに関連するメモリアクセス遅延を表しうる。
【００４４】
これらの割り当てられた重みを使って、コンパイラ２０２は現在ノードに隣接ノードに割り当てられている色を割り当てる際に、現在ノードと隣接ノードをつなぐ辺が、該現在ノードとその隣接ノードとをつなぐすべての辺のうちで最小の重みをもつ、よってパフォーマンスに対する影響が最小のハードウェア資源衝突を表す辺になるようになされうる。複数の辺が最小の重みを有していた場合には、ある実施形態では、これらの辺の一つが任意に選択されうる。別の実施形態では、該辺の一つが上記したようにメモリ使用を最小にするよう選択されうる。
【００４５】
ある実施形態では、たとえば、辺EDGE1（３１０）、EDGE2（３１２）、EDGE3（３１４）のパフォーマンス上のペナルティは、ハードウェア資源衝突に起因する足踏み（stall）実行サイクルに衝突する命令の実行数を乗じたものとして計算されうる。ある実施形態では、図９を参照すると、共同色セットは二つの色C1（４１２）およびC2（４１４）を有しうる。ノード３０２は色C1（４１２）を割り当てられており、ノード３０６は色C2（４１４）を割り当てられており、ノード３０４はまだ色を割り当てられていない。この例では、共同色セット中の色が両方ともノード３０４の隣接ノードに割り当てられているため、対応色セット４１０Ｂ中には利用できる色はないと想定できる。あるデータバンク衝突が６サイクルの遅延を引き起こし、EDGE1（３１０）によってつながれているノード３０２およびノード３０４に対応するデータDATA1（３５２）およびDATA2（３５４）にアクセスする命令I1およびI2が全部で1000回実行される場合、EDGE1（３１０）は1000×6＝6000のパフォーマンス上のペナルティを割り当てられうるので、EDGE1（３１０）の重みは6000などとなる。EDGE2（３１２）がEDGE1（３１０）より大きな重みを有している場合、ノード３０４に割り当てられる色C1（４１２）、C2（４１４）は、ノード３０２に割り当てられた色C1（C1（４１２））でありうる。ノード３０２は、最小の重みをもつ辺EDGE1（３１０）によってノード３０４につながれているノードだからである。
【００４６】
〈例〉
初期には、対応色セット４１０Ａ、４１０Ｂ、４１０Ｃ、４１０Ｄが各ノード３０２、３０４、３０６、３０８についてそれぞれ作成されうる。各対応色セット４１０Ａ、４１０Ｂ、４１０Ｃ、４１０Ｄは初期には共同色セット４１０からのすべての色を含んでいることができる。ある実施形態では、色付けされた衝突グラフが、以下の例示的なアルゴリズムを使って作成されうる。
１．前記複数のノード３０２、３０４、３０６、３０８のうちに少なくとも一つの色付けされていないノードがある場合、一つを現在ノードとして選択する。ノードの選択は任意でもよいし、あるいは下記で議論するようにノード３０２、３０４、３０６、３０８に割り当てられた優先度に基づいていてもよい。説明の目的のため、ノード３０２、３０４、３０６、３０８は次の順番に色を付けられうる：ノード３０２、ノード３０４、ノード３０６、ノード３０８．
２．現在ノードに対応色セットが空でなければそこから色を割り当てる。空だった場合には、現在ノードに最小重みの衝突色である色を割り当てる。
コンパイラは色セットからの色を任意に割り当てうる。代替的に、コンパイラ２０２はメモリ使用を最小にする色セットからの色を割り当てうる。説明の目的のため、データ要素のデータサイズは８バイトであり、ブロックサイズは１６バイトであるとする。
３．現在ノードに隣接する色付けされていない各ノードについて、現在ノードに割り当てられている色を該隣接ノードに対応色セットから除去する。
【００４７】
図４〜図７を参照すると、ノード３０２、３０４、３０６、３０８は以下のように色付けられうる：
１．少なくとも一つの色付けされていないノードがあるので、コンパイラ２０２はノード３０２を現在ノードとして指定しうる。それは、色C1（４１２）、C2（４１４）、C3（４１６）を有する色セット４１０Ａに関連付けられていることができる。
２．コンパイラ２０２はノード３０２に任意に色C1（４１２）を割り当てうる。代替的に、コンパイラ２０２は色セット４１０Ａのうちメモリ使用を最小にする色を割り当ててもよい。すべての色C1（４１２）、C2（４１４）、C3（４１６）はデータサイズ０に対応している（どの色もまだデータ要素に割り当てられていないので）ので、すべての色のデータサイズはブロックサイズで割ったときに整数になる。色セット４１０Ａ内の諸色は同じデータサイズに対応するので、該諸色のいずれもメモリ使用を最小にするために選択しうる。ノード３０２は色４０２を割り当てられている。
【００４８】
ノード３０４は色付けされておらず、ノード３０２に隣接している（ノード３０４はノード３０２とEDGE1（３１０）によってつながれている）ので、色C1（４１２）がノード３０４に対応色セットである色セット４１０Ｂから除去されうる。すると色セット４１０Ｂは色C2（４１４）およびC3（４１６）を含みうる。
【００４９】
図５に示されるように、ノード３０４は次のようにして色付けされうる：
１．少なくとも一つの色付けされていないノードがあるので、コンパイラ２０２はノード３０４を現在ノードとして指定しうる。それは、色C2（４１４）、C3（４１６）を有する色セット４１０Ｂに関連付けられていることができる。
２．コンパイラ２０２はノード３０４に任意に色C2（４１４）を割り当てうる。代替的に、コンパイラ２０２は色セット４１０Ｂのうちメモリ使用を最小にする色を割り当ててもよい。色C2（４１４）およびC3（４１６）はデータサイズ０に対応している（どちらの色もまだデータ要素に割り当てられていないので）ので、両方の色のデータサイズはブロックサイズで割ったときに整数になる。色セット４１０Ｂ内の諸色は同じデータサイズに対応するので、どちらの色もメモリ使用を最小にするために選択しうる。ノード３０４は色５０４を割り当てられている。
３．ノード３０６は色付けされておらずノード３０４に隣接するので（ノード３０６はノード３０４にEDGE2（３１２）によってつながれている）、色C2（４１４）がノード３０６の対応色セットである色セット４１０Ｃから除去されうる。すると色セット４１０Ｃは色C1（４１２）およびC3（４１６）を含むことになりうる。
【００５０】
図６に示されるように、ノード３０６は次のようにして色付けされうる：
１．少なくとも一つの色付けされていないノードがあるので、コンパイラ２０２はノード３０６を現在ノードとして指定しうる。それは、色C1（４１２）、C3（４１６）を有する色セット４１０Ｃに関連付けられていることができる。
２．コンパイラ２０２はノード３０６に任意に色C1（４１２）を割り当てうる。代替的に、コンパイラ２０２は色セット４１０Ｃのうちメモリ使用を最小にする色を割り当ててもよい。色C1（４１２）はデータサイズ８バイトに対応している（この色は１つのデータ要素DATA1（３５２）に割り当てられているので）ので、色C1（４１２）のデータサイズはブロックサイズで割ったときに整数にならない。色C3（４１６）はデータサイズ０に対応している（この色はまだデータ要素に割り当てられていないので）ので、色C3（４１６）のデータサイズはブロックサイズで割ったときに整数になる。結果として、色C1（４１２）がメモリ使用を最小化し、選択されうる。ノード３０６は色６０６を割り当てられている。
３．ノード３０８はノード３０６に隣接するので（ノード３０８はノード３０６にEDGE3（３１４）によってつながれている）、色C1（４１２）がノード３０８の対応色セットである色セット４１０Ｄから除去されうる。すると色セット４１０Ｄは色C2（４１４）およびC3（４１６）を含むことになりうる。
【００５１】
図７に示されるように、ノード３０８は次のようにして色付けされうる：
１．少なくとも一つの色付けされていないノードがあるので、コンパイラ２０２はノード３０８を現在ノードとして指定しうる。それは、色C2（４１４）、C3（４１６）を有する色セット４１０Ｄに関連付けられていることができる。
２．コンパイラ２０２はノード３０８に任意に色C3（４１６）を割り当てうる。代替的に、コンパイラ２０２は色セット４１０Ｄのうちメモリ使用を最小にする色を割り当ててもよい。色C2（４１４）はデータサイズ８バイトに対応している（この色は１つのデータ要素DATA2（３５４）に割り当てられているので）ので、色C2（４１４）のデータサイズはブロックサイズで割ったときに整数にならない。色C3（４１６）はデータサイズ０に対応している（この色はまだデータ要素に割り当てられていないので）ので、色C3（４１６）のデータサイズはブロックサイズで割ったときに整数になる。結果として、色C2（４１４）がメモリ使用を最小化し、選択され、ノード３０８に割り当てられうる。ノード３０８は色７０８を割り当てられている。
３．ノード３０８に隣接する色付けされていないノードはない。
【００５２】
すべてのノードに色が付けられているので、これ以上現在ノードは指定されない。色付けされた衝突グラフ７００は、データ要素３５２、３５４、３５６、３５８を配置するために使用されうる。
【００５３】
図４〜図７に示された例では、もしたとえばノード３０４の対応色セット４１０Ｂが空だった場合、ある実施形態では、重みが最小の衝突色が選択されることができる。図９を参照すると、EDGE2（３１２）に関連付けられた重みW2（９１２）はEDGE1（３１０）に関連付けられた重みW1（９１０）よりも小さいとすると、ノード３０２に対応する色（すなわち色C1（４０２））がノード３０４についての重みが最小の衝突色として選択されることになる。
【００５４】
〈色を付けるノードの選択〉
図９に示されるように、衝突グラフ３００内の各ノード３０２、３０４、３０６、３０８は優先度（priority）P1（９２２）、P2（９２４）、P3（９２６）、P4（９２８）を割り当てられ、該優先度P1（９２２）、P2（９２４）、P3（９２６）、P4（９２８）に従って順位付けされうる。本発明の実施形態では、ノードの優先度P1（９２２）、P2（９２４）、P3（９２６）、P4（９２８）は、そのノードの最も重みのある辺の重みとして計算されうる。たとえば、辺EDGE1（３１０）、EDGE2（３１２）、EDGE3（３１４）のおのおのが重みW1（９１０）、W2（９１２）、W3（９１４）をそれぞれ有していて、W1（９１０）＞W2（９１２）＞W3（９１４）だとすると：
ノード３０２に割り当てられる優先度P1（９２２）はW1（９１０）となりうる。EDGE1（３１０）がその唯一の辺であり、これは重みW1（９１０）を有するからである。
【００５５】
ノード３０４は２つの辺を有する：EDGE1（３１０）は重みW1（９１０）を有し、EDGE2（３１２）は重みW2（９１２）を有する。ノード３０４が割り当てられる優先度P2（９２４）はW1（９１０）となりうる。W1（９１０）がノード３０４につながれているすべての辺のうちで最も重みのある辺EDGE1（３１０）の重みだからである。
【００５６】
ノード３０６は２つの辺を有する：EDGE2（３１２）は重みW2（９１２）を有し、EDGE3（３１４）は重みW3（９１４）を有する。ノード３０６が割り当てられる優先度P3（９２６）はW2（９１２）でありうる。W2（９１２）がノード３０６につながれているすべての辺のうちで最も重みのある辺EDGE2（３１２）の重みだからである。
【００５７】
ノード３０８が割り当てられる優先度P4（９２８）はW3（９１４）となりうる。EDGE3（３１４）がその唯一の辺であり、これは重みW3（９１４）を有するからである。
【００５８】
各ノードはその優先度に従って順位付けされうる。同じ優先度をもつノードは任意に順位付けされうる。ある実施形態では、ノードは最高の優先度から最低の優先度の順に順位付けされうる。たとえば、ノード３０２およびノード３０４は順位１（９０２）および順位２（９０４）をそれぞれ与えられうる。両者がもつ優先度P1（９２２）、P2（９２４）はW1（９１０）で、他の優先度P3（９２６）、P4（９２８）よりも大きいからである。代替的に、ノード３０２およびノード３０４は順位２（９０２）および順位１（９０４）をそれぞれ与えられてもよい。その優先度P1（９２２）およびP2（９２４）が等しいからである。ノード３０６は順位３（９０６）を与えられうるし、ノード３０８は順位４（９０８）を与えられうる。ノード順位は、順位の順番にノードに色を割り当てるために使用されうる。ノード３０２、３０４、３０６、３０８に順位の順番に色C1（４１２）、C2（４１４）、C3（４１６）を割り当てることによって、最大の衝突を持つノード３０２、３０４、３０６、３０８が対応色セット４１０Ａ、４１０Ｂ、４１０Ｃ、４１０Ｄから色C1（４１２）、C2（４１４）、C3（４１６）を割り当てられる可能性が高くなり、それにより高衝突ノードに隣接ノードと同じ色が割り当てられる可能性が低下する。したがって、これはハードウェア資源衝突を軽減および／または解消する助けとなりうる。
【００５９】
〈色付けされた衝突グラフに基づくデータの配置〉
図８に示されるように、色付けされた衝突グラフ７００はデータ配置８００を生成するために使用されうる。ここでの用法では、「データ配置」とはデータ要素３５２、３５４、３５６、３５８のようなデータ要素の、メモリ２０６中のメモリ位置２１４のようなメモリ中のメモリ位置への割り当てのことをいう。説明の目的のため、各データ要素は８バイトであるとする。たとえば図１０では、コンパイラ２０２はたとえばメモリ位置0〜15および256〜271がデータバンク１００２Ａに、メモリ位置16〜31および272〜287がデータバンク１００２Ｂに、メモリ位置240〜255および496〜511がデータバンク１００２Ｎに対応することを知っているので、それはデータ要素３５２、３５４、３５６、３５８を次のようにして色付けされた衝突グラフ７００に従ってマッピングしうる：
１．ノード３０２、３０４、３０６、３０８について、それぞれの割り当てられた色に対応するデータバンク１００２Ａ、１００２Ｂ、…、１００２Ｎを割り当てる。ノード３０２、３０４、３０６、３０８にデータバンク１００２Ａ、１００２Ｂ、…、１００２Ｎが割り当てられるというのは、ノード３０２、３０４、３０６、３０８に対応するデータ要素DATA1（３５２）、DATA2（３５４）、DATA3（３５６）、DATA4（３５８）が、割り当てられたデータバンク１００２Ａ、１００２Ｂ、…、１００２Ｎにマッピングされるメモリ位置に割り当てられうるということを意味する。
２．ノード３０２、３０４、３０６、３０８に関連付けられたデータ要素DATA1（３５２）、DATA2（３５４）、DATA3（３５６）、DATA4（３５８）を、データバンク１００２Ａ、１００２Ｂ、…、１００２Ｎにマッピングされるメモリ位置に割り当てる。メモリ使用を最小にするため、要求されたデータバンクにマッピングされる最初の利用可能なメモリ位置が選択されうる。
【００６０】
図８を参照すると、データバンクBANK0（１００２Ａ）が色C1（４１２）に対応し、データバンクBANK1（１００２Ｂ）が色C2（４１４）に対応するならば、対応するデータ要素DATA1（３５２）、DATA2（３５４）、DATA3（３５６）、DATA4（３５８）は以下のようにして配置される：
ノード３０２は次のように処理されうる：
１．ノード３０２は色C1（４１２）を割り当てられており、色C1（４１２）はBANK0（１００２Ａ）に対応するので、データバンクBANK0（１００２Ａ）をノード３０２に割り当てる。ノード３０２に対応するデータ要素DATA1（３５２）は、データバンクBANK0（１００２Ａ）にマッピングされるメモリ位置（すなわち、0〜15、256〜271）に割り当てられうる。
２．ノード３０２に関連付けられているデータ要素DATA1（３５２）をメモリ位置0〜7に割り当てる。該メモリ位置はデータバンクBANK0（１００２Ａ）にマッピングされる最初の利用可能なメモリ位置である。
【００６１】
ノード３０４は次のように処理されうる：
１．ノード３０４は色C2（４１４）を割り当てられており、色C2（４１４）はBANK1（１００２Ｂ）に対応するので、データバンクBANK1（１００２Ｂ）をノード３０４に割り当てる。ノード３０４に対応するデータ要素DATA2（３５４）は、データバンクBANK0（１００２Ａ）にマッピングされるメモリ位置（すなわち、16〜31、272〜287）に割り当てられうる。
２．ノード３０４に関連付けられているデータ要素DATA2（３５４）をメモリ位置16〜23に割り当てる。該メモリ位置はデータバンクBANK1（１００２Ｂ）にマッピングされる最初の利用可能なメモリ位置である。
【００６２】
ノード３０６は次のように処理されうる：
１．ノード３０６は色C1（４１２）を割り当てられており、色C1（４１２）はBANK0（１００２Ａ）に対応するので、データバンクBANK0（１００２Ａ）をノード３０６に割り当てる。ノード３０６に対応するデータ要素DATA3（３５６）は、データバンクBANK0（１００２Ａ）にマッピングされる利用可能なメモリ位置（すなわち、8〜15、256〜271）に割り当てられうる。
２．ノード３０６に関連付けられているデータ要素DATA3（３５６）をメモリ位置8〜15に割り当てる。該メモリ位置はデータバンクBANK0（１００２Ａ）にマッピングされる最初の利用可能なメモリ位置である。
【００６３】
ノード３０８は次のように処理されうる：
１．ノード３０２は色C2（４１４）を割り当てられており、色C2（４１４）はBANK1（１００２Ｂ）に対応するので、データバンクBANK1（１００２Ｂ）をノード３０８に割り当てる。ノード３０８に対応するデータ要素DATA4（３５８）は、データバンクBANK1（１００２Ｂ）にマッピングされる利用可能なメモリ位置（すなわち、24〜31、272〜287）に割り当てられうる。
２．ノード３０８に関連付けられているデータ要素DATA4（３５８）をメモリ位置24〜31に割り当てる。該メモリ位置はデータバンクBANK1（１００２Ｂ）にマッピングされる最初の利用可能なメモリ位置である。
【００６４】
ここで、データバンクBANK2が色C3（４１６）に対応していてもよく、色C3（４１６）に割り当てられうるいかなるノード３０２、３０４、３０６、３０８も、対応するデータ要素３５２、３５４、３５６、３５８をデータバンクBANK2に割り当てさせることができるということを注意しておいてもいいだろう。しかし、BANK2は図８および図１０では明示的に示されていない。
【００６５】
データ配置８００を使って、機械実行可能命令３２８、３３０、３３２、３３４、３３６、３３８のシーケンスのプロセッサ２０８による実行が、プログラム実行の間データバンク衝突なく行われうる。
【００６６】
たとえば、実行サイクルY1（３１６）において、命令I1（３２８）はデータ要素DATA1（３５２）にアクセスし、命令I2（３３０）はデータ要素DATA2（３５４）にアクセスする（図３参照）場合を考え、そして各データバンクが実行サイクルあたり一つのデータ要求しか処理し得ないとすると、任意のデータ配置を使用すると、データ要素DATA1（３５２）およびDATA2（３５４）を同じデータバンクにマッピングされるメモリ位置（すなわち、それぞれメモリ位置0〜7および8〜15）に割り当てる結果を生じうる。よって、命令I1（３２８）およびI2（３３０）が同じサイクルにおいてDATA1（３５２）およびDATA2（３５４）にアクセスしようとするとき、遅延が生じうる。データバンクはサイクルあたり一つのデータ要求しか処理できないので、前記データ要素が両方とも同じサイクルの間にアクセスされることができないからである。
【００６７】
本発明の実施形態（図８参照）では、データ要素DATA1（３５２）はBANK0（１００２Ａ）を使ってアクセスされうるし、データ要素DATA2（３５４）はBANK1（１００２Ｂ）を使って同じサイクルにおいてアクセスされうる。各バンクが一つのデータ要求しか受け取らないおかげである。この例では、結果として、潜在的なハードウェア資源衝突が回避される。
【００６８】
〈結語〉
よって、ある実施形態では、方法は、機械実行可能命令のシーケンスをスケジューリングし、前記機械実行可能命令のシーケンスに基づく色付けされた衝突グラフに基づいてデータ要素のデータ配置を作成する、ことを含む。
【００６９】
衝突グラフを作成して該衝突グラフにおいて各ノードに色を割り当てることによって、ハードウェア資源衝突の危険が大幅に軽減され、および／または場合によっては解消されうる。ハードウェア資源衝突がまだ起こりうる場合には、それらの衝突の影響を起こる前に解析することによってそれらの衝突の影響が大幅に軽減されうる。従来技術とは異なり、本発明の諸実施形態は、コンパイラが命令を依存関係と実行ユニット資源が許す限り早くにスケジューリングするのを制限しない。さらに、本発明の実施形態は、データ配置が命令スケジューリングの際に知られていないときでも使用することができる。
【００７０】
以上の明細において、本発明は特定の実施形態を参照しつつ記述されてきた。しかし、それらの実施形態にはそれから外れることなくさまざまな修正および変更をなし得ることは明らかであろう。したがって、明細と図面は限定的な意味ではなく解説的な意味において見なされるべきものである。
【図面の簡単な説明】
【００７１】
【図１】システムを示す図である。
【図２】ある実施形態に基づくシステム実施例を示す図である。
【図３】例示的な実施形態の例を示す図である。
【図４】例示的な実施形態の例を示す図である。
【図５】例示的な実施形態の例を示す図である。
【図６】例示的な実施形態の例を示す図である。
【図７】例示的な実施形態の例を示す図である。
【図８】例示的な実施形態の例を示す図である。
【図９】例示的な実施形態の例を示す図である。
【図１０】ブロック巡回マッピングを示す図である。
【図１１】第一の実施形態に基づく方法を示すフローチャートである。
【図１２】第一の実施形態に基づくもう一つの方法を示すフローチャートである。
【図１】
2007517324.tif 000003
【図２】
2007517324.tif 000004
【図３】
2007517324.tif 000005
【図４】
2007517324.tif 000006
【図５】
2007517324.tif 000007
【図６】
2007517324.tif 000008
【図７】
2007517324.tif 000009
【図８】
2007517324.tif 000010
【図９】
2007517324.tif 000011
【図１０】
2007517324.tif 000012
【図１１】
2007517324.tif 000013
【図１２】
2007517324.tif 000014
【国際調査報告】
2007517324.tif 000015
2007517324.tif 000016
2007517324.tif 000017