(57)【特許請求の範囲】
【請求項１】
複数のメモリバンクで構成され、ｎ個のメモリアクセス要求を処理できるｎポートの入出力部がある記憶手段と、
該記憶手段に対してｎ個を超える同一バンクへのメモリアクセス要求が同時に発生したときに起こるバンク競合に関し、該バンク競合を起こすメモリアクセス命令の組を予測する予測手段と、
を有するプロセッサシステムであって、
前記予測手段は、過去のバンク競合履歴をプログラム中の各命令もしくは命令群を一意に特定することのできる識別子と共に保持するバンク競合履歴表と、
該バンク競合履歴表から各命令もしくは命令群の識別子によりバンク競合履歴を引き出し、これを用いてバンク競合を起こすメモリアクセス命令もしくは命令群の組を予測する手段と、
を備えることを特徴とするプロセッサシステム。
【請求項２】
複数のメモリバンクで構成され、ｎ個のメモリアクセス要求を処理できるｎポートの入出力部がある記憶手段と、
該記憶手段に対してｎ個を超える同一バンクへのメモリアクセス要求が同時に発生したときに起こるバンク競合に関し、該バンク競合を起こすメモリアクセス命令の組を予測する予測手段と、
複数の命令もしくは命令群をプログラムの順序に対して順不同に発行する命令発行手段と、を有するプロセッサシステムであって、
前記命令発行手段は、前記記憶手段に対するメモリアクセス命令もしくは命令群がアクセスするメモリアドレスが決定する前に、前記予測手段の予測結果を利用して、同一バンクへのメモリアクセス要求が同時に処理可能なアクセス数を上回って同時に起こらないように命令もしくは命令群の発行順序を制御する制御手段
を備えることを特徴とするプロセッサシステム。
【請求項３】
複数のメモリバンクで構成され、ｎ個のメモリアクセス要求を処理できるｎポートの入出力部がある記憶手段と、
該記憶手段に対してｎ個を超える同一バンクへのメモリアクセス要求が同時に発生して生じるバンク競合を検出する手段と、
前記検出手段の検出出力により更新され、プログラム中の各命令もしくは命令群を一意に特定することのできる識別子と共に過去のバンク競合履歴を保持するバンク競合履歴表と、
前記バンク競合を起こすメモリアクセス命令の組を予測する第１の予測手段と、
前記バンク競合履歴表から各命令もしくは命令群の識別子によりバンク競合履歴を引き出し、これを用いてバンク競合を起こすメモリアクセス命令もしくは命令群の組を予測する第２の予測手段と、
を備えることを特徴とするプロセッサシステム。
【請求項４】
前記検出手段は、バンク競合を起こした命令もしくは命令群の組におけるそれぞれの命令もしくは命令群の識別子間の関係に関する情報を出力する手段をさらに有し、
前記第２の予測手段は、前記命令もしくは命令群の識別子間の関係に関する情報を保持し、前記情報を元にバンク競合を起こすメモリアクセス命令もしくは命令群の組を予測することを特徴とする請求項３記載のプロセッサシステム。
【発明の詳細な説明】
【０００１】
本発明は、コンピュータ・プロセッサ・アーキテクチャに関し、特に順不同（out-of-order）に複数の命令もしくは命令群を同時に実行するプロセッサからマルチバンクのキャッシュメモリへ発行する複数のメモリアクセス命令もしくは命令群の選択において、バンク競合が起こらないと予測される命令もしくは命令群の組を選択して発行することにより、キャッシュメモリのデータ・スループットを増加させ、それによってプロセッサ・システムの性能を高める命令選択発行装置およびバンク競合予測装置を備えたプロセッサシステム装置に関する。
【０００２】
【従来の技術】
一般に、コンピュータ・プロセッサ・システムは、システムの処理を指示する制御ユニット、および計算演算を行う算術論理ユニット、および命令とデータをメモリシステムとの間で転送するメモリユニットからなる。プロセッサは、メインメモリに保存されている命令列からなるプログラムをメモリユニットを介して読み込み、このプログラムによって指示される処理によって制御ユニットが動作しデータパスの構築・算術論理ユニットの構成が行われ、メモリユニットを介して転送したデータを算術論理ユニットに流すことで処理を行う。このような動作を１単位とし、１命令ごとにこの動作を繰り返し行っていくことでプログラムを実行する。
高性能なプロセッサ、例えばスーパースカラ・プロセッサ等においては、このような１単位の動作を同時に複数の命令に対して行うことが可能なアーキテクチャ構成となっている。このようなプロセッサでは、性能を高めるために、プログラムに記述された命令の順序によらずに、発行可能な命令から順次、順不同に発行していく機構(out-of-order機構)に基づいて設計することができる。従来の技術では、フェッチした複数の命令を一時的に保持するバッファに蓄え、そのバッファに保持されている命令から発行可能な命令を探して発行していく方式をとるのが通常である。このとき、ある命令が発行可能であると判定するのに、必要なデータが揃っているかどうかを判定基準として利用する。また同時に発行可能な命令数よりも多くの命令が発行可能である場合には、通常プログラム順でより前に位置しているものから発行する。
複数命令を順不同に発行するプロセッサでは、メモリユニットをメモリアクセス命令を同一サイクル中に複数個実行可能な構成にすることができる。またメモリシステムにおいては、プロセッサとメインメモリの間にキャッシュメモリを設け、メインメモリ中のデータに対する高速なバッファとして利用される。キャッシュメモリには、プロセッサで利用された、もしくは利用されているか、今後利用されるデータがメインメモリもしくはプロセッサから転送されている。キャッシュメモリは、性能の最適化を目指して、複数のメモリアクセスを同時に処理できるようにするため、キャッシュメモリを複数のバンクに分けたマルチバンク構成にすることができる。
しかし、マルチバンク・キャッシュメモリであっても、同一バンクへのアクセス要求が同時に起こったとき、キャッシュメモリが1ポートであったりして同一サイクルに同一バンクでは１つのアクセス要求のみしか処理できない場合には、一方のアクセス要求は遅延することになる。このような問題(バンク競合)により、プロセッサとキャッシュメモリの間のデータ・スループットが低下し、プロセッサシステム全体の性能を高めることが困難になる。
【０００３】
【発明が解決しようとする課題】
アウトオブオーダ（out-of-order）スーパースカラ方式のように複数の命令もしくは命令群を順不同に実行する構成をとるのは、プロセッサの高性能化のために必然である。一方、プロセッサの動作周波数の向上により性能向上をはかる方法もあわせて取られるのが普通であり、方式の複雑化も含めて設計の困難さは上昇するばかりである。また、スーパースカラ方式のプロセッサでは、メモリアクセス効率の向上のために、複数のメモリアクセス命令もしくは命令群を同時に実行する機構の実装を行う場合があり、このときに同一バンクへのアクセス要求によるバンク競合の問題が発生することがある。バンク競合によりプロセッサとキャッシュメモリの間のデータ・スループットが低下するため、演算に必要なデータの転送が遅れる等の影響により、プロセッサシステム全体の性能を低下させてしまう問題が生じる。さらに、従来アウトオブオーダ・スーパースカラ・プロセッサ等のように複数のメモリアクセス命令もしくは命令群を順不同に複数発行するプロセッサでは、メモリアクセス命令もしくは命令群のアクセスするアドレスを計算した後にバンク競合を検出し、その後で競合した命令もしくは命令群を再実行や一時的に停止させるなどの対処をしていた。そのため、メモリアクセス命令もしくは命令群を処理する制御ユニットで無駄な処理を行うこととなり、このユニットの利用効率が低下するという問題が生じる。このようなバンク競合問題に対しては、キャッシュメモリのアクセスポート数を複数設ける解決策があるものの、複数ポート化にはハードウェア的な問題が多く存在する。この問題の１つに、複数ポート化による単位バイト当たりのキャッシュメモリを実装する面積の増大がある。限られた実装面積において、それをキャッシュメモリの複数ポート化にあてることは、キャッシュメモリの容量を減少させるという悪影響を与える。キャッシュメモリの複数ポート化によらない、バンク競合問題に対するもう１つの解決策としては、特開平９−１４７５６３号公報に示されているようなアクセスポートの時分割利用方式がある。この方式では、物理的なアクセスポート数は１つであるが、これを１サイクル中に複数回(ｎ回)使用することで論理的に複数ポートと同様の機構であるように見せるものである。この方式ではキャッシュメモリの実装面積は１ポートのキャッシュメモリとほぼ同じ大きさに押さえられるものの、１アクセス要求当たりの読み出し／書き込みのサイクル時間が１／ｎになるため、処理の遅延時間(ディレイ)に対する要求が厳しくなる。プロセッサの動作周波数の向上がますます進み、今後も動作周波数の向上を前提とした設計を考えた場合、ディレイに対する要求が厳しくなることは、実装の困難さを著しく上げることになる。以上に述べたバンク競合問題に対する解決策では、キャッシュメモリ容量増大への要求・プロセッサ動作周波数の向上への要求という２つの要求に同時に応えることは困難である。そこで、本発明の一つの課題は、単位バイト当たりのキャッシュメモリを実装する面積を増大させず、さらにディレイに対する要求を１サイクル当たり１アクセスに押さえながら、バンク競合問題を解決することにある。また、別の課題は、バンク競合により、メモリアクセス命��を処理する制御ユニットの利用効率を低下させないバンク競合回避を実現することにある。なお一般には、メモリのアクセスポート数が２以上であっても、同時に発行されるメモリアクセス要求数がメモリのアクセスポート数を上回る場合に、バンク競合問題は発生する。よって、本発明が解決しようとする上記２つの課題は、言いかえると、同時に発行されるメモリアクセス要求数がメモリのアクセスポート数を上回る場合に、バンク競合問題による性能低下を削減することと言うことができる。
【０００４】
【課題を解決するための手段】
上述した２つの課題を解決するために、本発明ではメモリアクセス命令もしくは命令群を順不同に複数発行する際に、これらのメモリアクセス命令もしくは命令群のアクセスするメモリアドレスが決定するよりも前に、これらのメモリアクセス命令もしくは命令群がアクセスするメモリアドレスが互いにバンク競合を起こすか否かを予測し、バンク競合を起こさないと予測されるメモリアクセス命令もしくは命令群を同時に発行する機構を設ける。
【０００５】
【発明の実施の形態】
図１は本発明の１実施例のプロセッサのメモリアクセス命令処理を示すブロック図である。命令フェッチユニット2はフェッチすべきアドレスをアドレスバス14を通して命令キャッシュ1に送信し、命令キャッシュ1から命令をフェッチする。各命令は、命令キャッシュ1から命令並び替えユニット3への命令の転送パス15を通して命令並び替えユニット3に転送される。命令並び替えユニット3では、フェッチされた命令を一時的に保存し、スコアボード6を用いて発行可能な命令を選択し、その命令を実行ユニット4に発行する。実行ユニット4では各命令の命令種に応じて、演算ユニット(整数・浮動小数点)7、メモリアクセスユニット8、分岐ユニット9などが用意される。メモリアクセスユニット8は、メモリアクセスバス19を通してメモリシステム5にアクセスするメモリアドレスを通知する。メモリシステム5は、１つもしくは複数のキャッシュメモリ10とメインメモリ11、およびそれらを結ぶ制御・データバス21で構成される。バンク競合検出器13は、実行ユニット4におけるメモリアクセスアドレスを監視するパス23もしくはメモリシステム5におけるメモリアクセスアドレスを監視するパス24を通して、メモリシステム5におけるバンク競合の検出を行う。バンク競合履歴表12はバンク競合検出器13からのバンク競合発生信号伝達パス25を通して伝えられるバンク競合の発生によってバンク競合の履歴を保持する表を更新する。そして、バンク競合履歴表12の情報から命令並び替えユニットに対して並び替え制御を支援する情報を伝えるパス21を通して並び替え制御の一部を行うことで、バンク競合の発生を低減させる。
本発明によって性能向上が見込めるメモリシステムの一例は図２に示すような、複数のメモリアクセス命令が同時に発行可能であり、メモリシステムが複数バンクで構成されるものである。メモリアクセスユニット8から２つの命令”命令１”と”命令２”がメモリシステムに対して発行され、各々のアクセスするメモリアドレスに応じてメモリシステム内の複数のバンク26〜29(bank1,bank2,bank3,bank4)のいずれか、もしくは複数のバンクにアクセスして１サイクルかけてデータの入出力を行う。各バンクの入出力ポート数が１で、命令１,命令２がそれぞれ１つのバンクにアクセスするとした場合、アクセスするバンクが同じバンクであるとバンク競合が発生し、いずれかの命令を遅延させることになる。
図２は２命令同時発行で１ポートメモリの４バンク構成であったが、図３のような４命令同時発行で２ポートメモリの４バンク構成であっても同様のバンク競合が発生することがある。一般にメモリの入出力ポート数を上回る数の命令が同時に発行されるシステムで同様の問題が発生する。
図４は図２のシステムにおいて、バンク競合が発生した場合と発生しなかった場合の、メモリアクセス命令の実行時間をタイムチャートで示したものである。バンク競合の発生により各サイクルに実行できる命令数が２から１に減少し、メモリアクセス命令のスループットが半分になる。また、メモリアクセス時のメモリバンク使用サイクル数(バンクビジーサイクル数)が複数サイクルの場合には、よりバンク競合が発生しやすくなる。
本実施例では、メモリアクセス命令のスループットを落とさないように、バンク競合が起こらないと予測されるメモリアクセス命令を組にして発行するための機構を追加する。実施例のバンク競合の予測を行う機構は、図５に示すように大きく分けて２つのブロックで構成される。１つはバンク競合の発生を監視するバンク競合検出器13で、もう１つはバンク競合の履歴を管理し、命令並び替えユニット3における並び替え制御の一部を行うバンク競合履歴表12である。
バンク競合検出器13には、実行ユニットからメモリシステムに発行するアクセス命令がアクセスするメモリアドレス情報やアクセスするバンク番号をメモリアクセス命令IDと共に受け取り、それを一時的に保持するためのアクセスアドレスバッファ30と、メモリシステム内のバンクごとのアクセス状態、もしくはメモリシステム内に用意されたバンクビジー時に一時的にアクセス要求を保持しておくキューの状態、およびアクセスしている命令のIDを受け取り、それを一時的に保持するためのバンク情報バッファ31を設け、これらのバッファの情報から同一バンクに対するアクセス要求の発生を検出、もしくはバンクビジーによるバンク競合の発生を検出するバンク競合検出回路34がある。
バンク競合履歴表12は、命令並び替えユニット3において、特に発行可能なメモリアクセス命令の中から複数の命令を選択して実行ユニットに発行する際に、どのメモリアクセス命令を組にして発行すべきかを決定するのに利用する。そのためにバンク競合履歴表12では、メモリアクセス命令IDとその命令のバンク競合履歴を保持し、その状態はバンク競合検出回路34からの競合発生信号伝達パス25に応じて更新される。
命令並び替えユニット3で、２つのメモリアクセス命令を同時に発行する際の発行手順は次の通りである。
(1)命令IDでバンク競合履歴表を引き、バンク競合履歴表から過去のバンク競合履歴を得る。
(2)命令並び替えユニット中の並び替えバッファに保存されている発行可能なメモリアクセス命令の中で実行優先度が最も高い命令のバンク競合履歴から、並び替えバッファ中の命令をその実行優先度順に、その命令と過去にバンク競合を起こしたことがない発行可能な命令がないか検索する。
(3)上記(2)で該当する命令が発見できなかった場合には、過去にバンク競合を起こしたことがある命令の中で最も実行優先度が高い命令と組にして発行する。
この発行制御は図５の発行命令選択回路35で行われる。この回路に組み込まれる論理の真理値表の一例が図６である。図６で入力とは、発行命令選択回路35への入力で、スコアボード6からの命令発行可能マスクとバンク競合履歴表12からのバンク競合履歴からなる。この例では、命令並び替えユニットに４つのメモリアクセス命令を一時的に保持する並び替えバッファがあるとする。図６で命令発行可能マスクは並び替えバッファ中の４命令が発行可能状態のときに１、発行不可能状態のときに０であるとし、命令１が最も実行優先度が高く、命令４が最も実行優先度の低い命令であるとする。また図６における、バンク競合履歴は命令１が過去にバンク競合を起こした後続命令に関する情報を示し、これが“００”の場合は、後続命令とはバンク競合を起こしていないことを示し。“０１”の場合は直後の命令とバンク競合を起こしたことがあることを、“１０”の場合は直後およびその後ろの合計２命令とバンク競合を起こしたことを、“１１”の場合はさらにその後ろの命令の合計３命令とバンク競合を起こしたことを示す。また“―”は無関係であることを示し、例えば“1―”は“１０”もしくは“１１”であることを意味する。図６で出力とは、命令並び替えユニットから実行ユニットに対して発行する命令の番号である。図６の発行命令番号＃１とは同時に発行される２命令の内の優先度の高い命令を、＃２は優先度の低い命令を示す。また“―”は発行する命令がないことを示す。例えば、図６の５行目の発行命令番号が＃１＝１、＃２＝３の場合を例に説明をする。
(1)命令１〜４はいずれも命令発行可能マスクが１であるので発行可能であり、命令１のバンク競合履歴は“０１”であるので、直後の命令つまり命令２とは過去にバンク競合を起こしたことがあることを示している。
(2)発行命令選択回路35はこれらの入力から、まず発行可能な命令の中で最も実行優先度が高い命令１を発行命令番号＃１として出力する。
(3)さらに命令１と組にして発行する命令として、次に優先度の高い命令２を検討するが、この命令２は過去に命令１とバンク競合を起こしているため、次に優先度の高い命令３を検討する。命令３は命令１と過去にバンク競合を起こしたことはないので、命令３を発行命令番号＃２として出力する。
図７はバンク競合履歴表12の構成の例を示したものである。バンク競合履歴表12は複数のエントリ39からなっており、各エントリ39は、命令IDを示すタグ37とバンク競合履歴38から構成される。タグ37は命令を特定するための情報で、この情報としては次のようなものを利用することができる。
(1)命令のメモリ上でのアドレス
(2)命令のプログラムカウンタ値
(3)上記(1)、(2)の値の一部
つまり各命令の特定が可能な命令IDとなるものが利用できる。命令IDは必ずしも一意に命令を特定できるものでなくてもよい。
バンク競合履歴38は、タグ37で示される命令のバンク競合履歴を保持するもので、その保持内容としては次のようなものを利用することができる。
(1)最近にバンク競合を起こした命令の命令ID。
(2)この命令の後続のＭ個の命令それぞれに１ビットを割り当て、バンク競合を起こした命令についてこのビットを１にする。
(3)命令並び替えバッファに保持できるＮ個の命令に対してｎビット（２ｎ＞Ｎもしくは２ｎ＝Ｎ）を用意する。この命令の後続の命令からｍ個の命令がいずれもバンク競合を起こした場合、このｎビットでｍを表現する。
(4)バンク競合を起こす可能性の高さをｐビットで表現する。最も簡単な例では１ビットでバンク競合を起こす可能性の高さを示し、このビットが１の場合には例えば後続のＰ個の命令とはバンク競合を起こす可能性があることを示す例が挙げられる。
図８はメモリアクセス命令の発行から完了およびバンク競合履歴表の更新までを含めた一連の処理フローの一例を示したものである。発行することを決定したメモリアクセス命令Ａに対し、この命令Ａと同時に発行するメモリアクセス命令Ｂを選択するには、バンク競合履歴表から得た命令Ａに関するバンク競合履歴（Ｈ）に対し、Ｈ＝ｎならば命令並び替えユニット3に登録されている命令Ａの後続のｎ命令を除いた命令群から、命令発行可能マスクを使って発行可能な命令をエントリ順に探す。発行可能な命令があった場合には、この命令を命令Ｂとし、状態変数コンフリクトビット（ＣＢ）を０（ＣＢ＝０）とする。発行可能な命令がなかった場合には、命令Ａの後続のｎ命令の中から発行可能な命令をエントリ順に探す。発行可能な命令があった場合は、この命令を命令Ｂとし、状態変数コンフリクトビット（ＣＢ）を１（ＣＢ＝１）とする。発行可能な命令がなかった場合には、命令Ａのみの単独発行となり、状態変数コンフリクトビット（ＣＢ）は０（ＣＢ＝０）とする。命令が発行され、図１のメモリアクセスユニット8でメモリアドレス計算が行われ、バンク競合検出器13で発行された命令Ａ・命令Ｂ間のバンク競合の検出が行われる。バンク競合が検出された場合には、状態変数コンフリクトビット（ＣＢ）の値によって処理が分岐する。ここでは、図７のバンク競合履歴38を、命令並び替えバッファに保持できるＮ個の命令に対してｎビット（２ｎ＞Ｎもしくは２ｎ＝Ｎ）を用意し、この命令の後続の命令からｍ個の命令がいずれもバンク競合を起こした場合、このｎビットでｍを表現する方法で実現したとする。ＣＢ＝０ならば、バンク競合履歴表12の命令Ａに該当するエントリのバンク競合履歴38を＋１する。ただし、すでにバンク競合履歴38のビットがすべて１の場合には変更をしない。ＣＢ＝１ならばバンク競合履歴表は更新しない。バンク競合が検出されず、かつＣＢ＝１の場合には、バンク競合履歴表12の命令Ａに該当するエントリのバンク競合履歴38を−１する。ただし、バンク競合履歴38のビットがすべて０の場合には変更をしない。
【０００６】
【発明の効果】
本発明の効果の１つは、マルチバンクキャッシュメモリの同一バンクへのアクセスによって生じるバンク競合問題を、キャッシュメモリ自体にハードウェア的な変更を加えることなく回避できることである。キャッシュメモリの実装面積は１ポートのキャッシュメモリと同様であるため、複数ポート化によってバンク競合問題を回避する方式に比べて単位Byte当たりの実装面積を小さくできるため、同じ実装面積でもより大きい容量のキャッシュメモリが実装可能になる。また時分割化によりバンク競合問題を回避する方式に比べてキャッシュメモリの制御にかかるディレイ制約が緩くできるため、プロセッサの動作周波数の向上においてキャッシュメモリへのアクセス・パスが設計上のクリティカルパスとなる可能性を低減することができる。
本発明の２つ目の効果は、複数のメモリアクセス命令を同時に実行するメモリアクセス命令処理ユニットに対して、バンク競合を起こす命令を同時に発行する確率が低減するので、処理ユニットにおいてバンク競合が検出される確率が減り、マルチバンクキャッシュメモリに対して複数のデータ転送要求を同時に発行できる可能性が向上するため、処理ユニットおよびキャッシュメモリの利用率が向上する点である。
本発明の３つ目の効果は、バンク競合の予測を命令発行時点で行えるため、メモリアクセスのアドレス計算をする前にバンク競合の予測ができ、パイプラインプロセッサにおいては、実行ステージよりも早い発行ステージでバンク競合の可能性を低減できることである。
【図面の簡単な説明】
【図１】本発明の実施例のメモリアクセス命令処理のブロック図である。
【図２】本発明を適用することにより性能向上が見込まれるメモリアクセスユニットおよびメモリシステムの構成図（２命令同時発行で１ポートメモリの４バンク構成）である。
【図３】本発明を適用することにより性能向上が見込まれるメモリアクセスユニットおよびメモリシステムの構成図（４命令同時発行で２ポートメモリの４バンク構成）である。
【図４】実施例のバンク競合発生時のメモリアクセス・タイミングチャートである。
【図５】実施例のバンク競合検出器およびバンク競合履歴表と命令並び替えユニットの構成図である。
【図６】実施例の発行命令選択回路における選択論理の真理値表である。
【図７】実施例のバンク競合履歴表の内部構成を示すブロック図である。
【図８】実施例のシステムにおけるメモリアクセス命令の処理フロー図である。
【符号の説明】
１：命令キャッシュ
２：命令フェッチユニット
３：命令並び替えユニット
４：実効ユニット・レジスタファイル
５：メモリシステム
６：スコアボード
７：演算ユニット(整数・浮動小数点)
８：メモリアクセスユニット
９：分岐ユニット
１０：キャッシュメモリ
１１：メインメモリ
１２：バンク競合履歴表
１３：バンク競合検出器
１４〜２５：内部接続パス
２６〜２９：メモリシステム内のバンク
３０：アクセスアドレスバッファ
３１：バンク情報バッファ
３２，３３：内部接続パス
３４：バンク競合検出回路
３５：発行命令選択回路
３６：内部接続パス
３７：バンク競合履歴表のタグ
３８：バンク競合履歴表のバンク競合履歴
３９：バンク競合履歴表のエントリ。
【図１】
0003956652.tif 000002
【図２】
0003956652.tif 000003
【図３】
0003956652.tif 000004
【図４】
0003956652.tif 000005
【図５】
0003956652.tif 000006
【図６】
0003956652.tif 000007
【図７】
0003956652.tif 000008
【図８】
0003956652.tif 000009