JP4745335B2 - 動的負荷バランシング - Google Patents

Description

本発明は、例えばマルチスレッド化されたマイクロプロセッサのスレッドへのメモリのような一つまたはそれより多いリソースへのアクセス帯域幅を動的に割り当てるための方法および装置に関する。メモリアクセスにおいて、これはメモリレイテンシを改善し、特に、集中的なメモリ動作の期間における自動ＭＩＰＳ配置（ＡＭＡ）制御システムの過負荷を防止する。

我々の英国特許出願９６０７１５３．５号は、マルチスレッド化されたプロセッサおよび複数の実行スレッドが、複数のデータ入力と複数のデータ出力の間で、データ処理手段を介して、ルーチングされるデータ処理管理システムについて説明する。このデータ処理手段は、データ記憶手段へのアクセスを有する。このシステムは、繰り返し、どのルーチング動作およびどのデータ処理動作が実行される能力を有するかを決定し、少なくとも一つのルーチングまたはデータ処理動作の実行を各クロック周期において開始する。

そういったマルチスレッド化されたプロセッサの典型的なサブモジュールが図１に示される。この例示の目的のため、この図におけるマイクロプロセッサ・コアは二つの実行スレッドだけを有する。

マイクロプロセッサ・コア１はメモリ要求をメモリ管理ユニット２へ発行する。この要求されたデータがそのローカルメモリ内にない場合（すなわち、キャッシュ・ミス）、その要求されたデータは外部メモリからフェッチされなければならないことが考えられる。外部メモリは単一のデータパスを有するだけであるため、プレ・アービター３は、異なるスレッドからの要求の間で仲裁を行なうために使用される。

図１において使用され得る最も単純な種類の仲裁方式は、ラウンド・ロビンである。しかし、そういった方式には二つの主要な問題がある。それらは以下のものである。

第１に、従来型のダイナミック・ランダム・アクセスメモリ（ＤＲＡＭ）は、複数のバンクとして組織される。これらのバンクはページと呼ばれる領域へ分割される。一般的には、メモリ位置へアクセスされ得る前に、関連するページがオープンされなければならない。アクセスの後、このメモリは現在のページをオープン（オープン・ページ・ポリシー）、またはクローズ（クローズ・ページ・ポリシー）し続けるかを選択することが考えられる。例えば、メモリがオープン・ページ・ポリシーにおいて動作し、プレ・アービターが、最後のアクセスと同じページ内に存在しないメモリアクセスを送信することを選択する場合、新規なページをオープンするために必要な時間量に起因して高いメモリ周期レイテンシが生じる。一方、メモリがクローズ・ページ・ポリシーにおいて動作している場合、最後と同じページ内のメモリ要求の送信が同様に高いレイテンシを生じる。

第２に、マルチスレッド化されたプロセッサのＡＭＡは、すべてのスレッド上において動作するすべてのプログラム処理要求が満たされるように、プロセッサリソースの使用を制御する問題を取り扱う。図１の仲裁手段はスレッドの現在の状態を考慮しない。これは、ＡＭＡの動作が妨げられるかもしれない可能性があることを意味する。特に、集中的メモリ動作期間が存在する場合、プレ・アービター３が単純にいかなるスレッドＡＭＡ情報をも有さないという事実に起因して、ＡＭＡ制御システムは過負荷となり得る。

本発明の好ましい実施形態は、一以上のスレッドがメモリアクセスを要求している場合において、メモリレイテンシを最適化することを目的とする。これを達成すべく、メモリによって受け入れられた最後のメモリアクセスのページアドレスを記憶するためにレジスタが使用される。アービター入力での各スレッドの各アクセスのために、個別のページアドレスが計算され、最後のメモリアクセスのページアドレスを記憶するためのレジスタにおいて保持されるページアドレスと比較される。それから、この比較は、ページ内インジケーションを生成するために使用され得る。それから、ページ内インジケーションをユーザ定義の重みに乗算し、メモリアクセスおよび異なるスレッド間のページ内最適化におけるユーザ制御を許容することで、様々なスレッドのページ内メトリックが導出される。オープンおよびクローズ・ページ・ポリシーの両方を伴うメモリは最適化され得ることに注意されたい。

第２の問題を解決するために、好ましい実施形態は、ＡＭＡメトリックと呼ばれるもう一つのメトリックを生成する。まず、ＡＭＡ遅延カウント、およびデッドラインカウント値のサブセットが取得される。これらの値は、ＡＭＡメトリックを生成するために操作される。各カウントのための各スレッドのためのサブセットは、メモリアクセスの仲裁に影響するＡＭＡ状態の範囲の制御を提供するために、ユーザによって個別的に選択可能である。

好ましい実施形態は、メモリへのスレッドアクセスに影響を及ぼすために、これら二つのメトリックを個別にまたは状態スレッド優先度と組み合わせて一緒に使用することを可能にする。

ここで、本発明の好ましい実施形態が、添付された図面を参照しつつ、例示の方法で詳細に述べられる。

図２はメモリ・プレ・アービター１を図解的に示す。これは、各スレッドのためのＡＭＡ入力を受信するＡＭＡ抜出ユニット４と、並列に各スレッドのためのメモリデータおよび制御入力を受信するページ内メトリック生成ユニット７とを備える。ＡＭＡ抜出ユニットおよびページ内メトリック生成ユニットの結果が、総合的メトリック生成ユニット５へ供給され、そしてそれから、どのスレッドがメモリへのアクセスを有するべきかを決定し、その出力においてこのアクセスを提供する仲裁ロジック６へ供給される。仲裁ロジック６は、それがデータをその出力を介してメモリへ渡すことを可能とするため、各スレッドのためのメモリデータおよび制御入力へも接続される。

ＡＭＡ抜出ユニット４は、サブセット選択操作および各スレッドのためのＡＭＡメトリックへの様々なＡＭＡカウントの連結を実行する。ページ内メトリック生成ブロック７は、最後のメモリページアドレスの記憶、入力要求のページアドレスとの比較、およびページ内メトリックを与えるために必要な操作を実行する。通常、この操作は単純に一つの操作を含む。

総合的メトリック生成ユニット５は、その最終的なスレッド決定を導出するために、仲裁ロジック６による使用のための各スレッドの総合的メトリックを生成するために必要なロジックすべてを含む。スレッドが、マルチスレッド化されたプロセッサ上で実行している場合、各スレッドは、ＡＭＡ入力と、メモリデータおよび制御データを、どのスレッドがメモリへのアクセスを有するべきかを決定するための仲裁ロジックによって使用される総合的メトリックを生成するために、ＡＭＡメトリックおよびページ内メトリックを抜出すメモリ・プレ・アービターに供給する。どのスレッドがメモリへのアクセスを有するかを決定するために、ＡＭＡメトリックかページ内メトリックまたは静的スレッド優先度だけが使用されるように、本発明は修正され得る。

図３は、スレッドのＮ番目のためのページ内メトリックブロックの実施を示す。最後のメモリアクセスレジスタ９は、図２の仲裁ロジック６によって外部メモリへ送信される最後のメモリ・トランザクションのメモリアドレスを記憶するために提供される。ページサイズレジスタ８は、アクセスされるメモリにおけるバイト表示のページサイズを表す定数を記憶する。比較器はそれぞれ、入力アドレスから各スレッドによって要求されるページアドレスを算出するために、ページサイズレジスタ８において記憶される値を使用する。次に、これは、レジスタ９において記憶された最終メモリアクセス値と比較される。それから、一つが各スレッドのためであるＮ個のページ内メトリックを与えるために、比較器の出力はユーザ指定のページ内重み付けによって乗算される。各ページ内重み付けは、同じサイズのページ内メトリックを与える８ｂｉｔ ｕｎｓｉｎｇｅｄのベクトルである。

このスレッド毎ページ内重み付けは、各スレッドのページ内効果が個別によく調整されることを可能とする。それはまた、すべてのスレッドの要求がページ内であるとき、例えば、関連のあるスレッド優先度を異なる値を各スレッドへ割り当てることで確立するような柔軟性を与える。

スレッドの一つのためのＡＭＡ抜出ブロックが図４に示される。他の実施形態においては異なる出力が適切であるかもしれないが、このブロックの目的はこの特定の実施形態におけるスレッド毎の８ｂｉｔ出力ベクトルを生成することである。この８ｂｉｔ出力ベクトルは、スレッドの現在のＡＭＡ状態を反映すべきである。ＡＭＡにおいて、スレッド順位付けアルゴリズムは、スレッドの総合的メトリックを比較することに基づく。これは、その時間までにスレッドが実行されなければならない時間であるＤＥＡＤＬＩＮＥ ＣＯＵＮＴ、スレッドの実行が最初に要求されてからの遅延であるＤＥＬＡＹ ＣＯＵＮＴ、およびスレッドに与えられた優先度である優先度の連結である。ＤＥＡＤＬＩＮＥ ＣＯＵＮＴは、これらのメトリックの中で最も重要である。したがって、このブロックのために使用するためのＡＭＡメトリックの一つの妥当な形式はより深刻なＤＥＡＤＬＩＮＥ ＣＯＵＮＴを伴うＤＥＡＤＬＩＮＥ ＣＯＵＮＴとＤＥＬＡＹ ＣＯＵＮＴの連結である。

二つのカウント値の全体長が使用された場合、極めて厳密なタイミング要求がプレ・アービターの以下のステージにおけるハードウェア上で課される。例えば、加算器と比較器は、懸命に動作しなければならないだろう。このタイミング要求を軽減するために、ＡＭＡ状態へのプレ・アービターの感度の許容可能かつ使用可能なレンジを許容している間、例えば、ＤＥＡＤＬＩＮＥおよびＤＥＬＡＹ ＣＯＵＮＴのそれぞれからのレングス４のビットスライスが、スライス選択ユニット１０によって取得される。図４からわかるように、この特定の例においては、４ｂｉｔスライスが２０ｂｉｔのＤＥＡＤＬＩＮＥ ＣＯＵＮＴおよび２７−ｂｉｔのＤＥＬＡＹ ＣＯＵＮＴから取得される。異なる大きさのスライスが、特に異なるサイズのＤＥＬＡＹおよびＤＥＡＤＬＩＮＥカウントとともに使用されるかもしれない。これがなされた後、これらのビットは、レンジ超過ロジック１１へ渡される。それは、スライスが本当にそれらのオリジナルの小型版を表していることを補償することを確認する。例えば、ビット５からビット２までのスライスが、（ＭＳＢ）ｘｘｘｘｘ１０００００００（ＬＳＢ）であるオリジナル値とともに取得された場合、最大限界でレンジ超過である値を示すために、そのスライスは１１１１の最大値へセットされるべきである。レンジ超過確認クロジック１１がこの機能を実行する。同様の処理が、ＤＥＬＡＹ ＣＯＵＮＴスライスにおいても実行される。この値がレンジ限界を超えていない場合、それは変更されない。この後、二つのスライスは、連結ユニット１２によって、そのスレッドのためのＡＭＡメトリックを生成するために連結される。

図５は、さらに詳細に、図２の総合的メトリック生成ユニット５を示す。これは、３つのメトリック入力を受信する加算器１３を備える。これらの第１は、スレッド実行のための８ｂｉｔ固定のユーザ定義のスレッド優先度である。ＡＭＡメトリックおよびページ内メトリックは他の二つの入力である。加算器の出力は９ｂｉｔであり、レンジ制限ロジック１４へ供給される。すべての８ｂｉｔ入力ベクトルが、９ｂｉｔ出力と同様にｕｎｓｉｇｎｅｄである。

各スレッドのために、個々の加算器１３は、上述のＡＭＡとページ内メトリックを固定のユーザ指定のスレッド優先度に加算する。それから、レンジ制限ロジックはその和を最大許容可能値へ制限する。この固定のスレッド優先度を含むことの目的は、ＡＭＡおよび／またはページ内データが使用されていないときに、プレ・アービターが固定のスレッド優先方式とともに動作することを可能とすることである。

上記提案された総合的なスレッド優先メトリックは、スレッド決定のために使用されることに適している。なぜなら、この値が高いほど、この要求の重要性が仲裁ロジックによって高いとみなされるであろうためである。例えば、ユーザはメモリレイテンシ特性を、特定のスレッドのために重要であるとみなすかもしれないことで、大きなページ内重みが設定され、それにより、ページ内最適化機会が到来すると、大きな総合的メトリックを生成する。ＡＭＡ制御のコンテキストにおいて、導出されたＡＭＡメトリックにおけるより高い値は、重くスケジュールされたスレッドに対応するかもしれない。これは、その通常のスケジューリングへ立ち戻るためにＡＭＡによって必要とされる時間を減少させるためにスレッドが高いメモリ帯域幅を有することを、プレ・アービターが確認することを可能とし、このようにして、このバランシング期間の間に他のスレッドのＡＭＡカウントが飽和する可能性を減少させる。

上述の総合的メトリックに基づいた仲裁方式を用いると、一つの実行スレッドも要求していない場合または少なくとも一つのスレッドは要求している場合の両方の場合において、周期的決定によって顕著かつ機能上正しい周期が生成されることは重要なことである。少なくとも二つの実行スレッドが同じメトリックを有する場合において、プレ・アービターは、例えば、ラウンドロビン仲裁方式を用いることでスレッドのそれぞれへのメモリ帯域幅の等しい割り当てを与えるべきであることもまた重要である。

図６は、図２におけるプレ・アービターの仲裁ロジックの構成を図示したものである。このブロックへの入力はｍ＿Ｔ０、ｍ＿Ｔ１、ｍ＿Ｔ２ならびにｍ＿Ｔ３（ここで、ｍ＿Ｔ０はスレッド０の総合的メトリックである）、および、ｖ＿Ｔ０、ｖ＿Ｔ１、ｖ＿Ｔ２ならびにｖ＿Ｔ３（ここで、ｖ＿Ｔ０における１はｍ＿Ｔ０が有効であることを示す）である。図６がどのように動作するのかを理解するために、サブブロックの動作についてまず説明する。

再並べ替えロジック１５の機能は、四つの入力のペア、ｍ＿Ｔ０（ｖ＿Ｔ０）・・・ｍ＿Ｔ３（ｖ＿Ｔ３）を異なる出力位置へ、各クロック周期において割り当てるためのものである。例えば、現在の周期において、
ｍ＿Ｔａ＝ｍ＿Ｔ０、ｍ＿Ｔｂ＝ｍ＿Ｔ１、ｍ＿Ｔｃ＝ｍ＿Ｔ２、ｍ＿Ｔｄ＝ｍ＿Ｔ３
ｖ＿Ｔａ＝ｖ＿Ｔ０、ｖ＿Ｔｂ＝ｖ＿Ｔ１、ｖ＿Ｔｃ＝ｖ＿Ｔ２、ｖ＿Ｔｄ＝ｖ＿Ｔ３
であり、次の周期において、
ｍ＿Ｔａ＝ｍ＿Ｔ１、ｍ＿Ｔｂ＝ｍ＿Ｔ２、ｍ＿Ｔｃ＝ｍ＿Ｔ３、ｍ＿Ｔｄ＝ｍ＿Ｔ０
ｖ＿Ｔａ＝ｖ＿Ｔ１、ｖ＿Ｔｂ＝ｖ＿Ｔ２、ｖ＿Ｔｃ＝ｖ＿Ｔ３、ｖ＿Ｔｄ＝ｖ＿Ｔ０
である。
このシフトと規則であってそれがその規則に基づく規則の目的は、この議論の中で後ほど明らかとなるであろう。

比較器ブロック１６の機能は、それらの有効性をｖ＿Ｔａ・・・ｖ＿Ｔｄによって与えられるｍ＿Ｔａ、ｍ＿Ｔｂ、ｍ＿Ｔｃ、およびｍ＿Ｔｄのなかで最も高い総合的メトリックを決定し、「スレッド決定」となるその対応するスレッド番号を出力する。図６におけるそういった単一の比較器１７の真理値表が以下に与えられる。Ａ０およびＡ１は、比較されるべき二つのデータ入力であり、Ｖ０およびＶ１はその有効性である。出力は、どれがサイズにおいてより大きいかに応じて、Ａ０またはＡ１を含む。

この表から、太字で示された列は一つだけの明確な出力を有することがわかる。例えば、第２段において、有効なＡ１と無効なＡ０を比較することはＡ１の出力を生成することとなる。太字で記されていないその他の列は、「どちらの実行スレッドも要求していない」、または「二つのメトリックが同じである」ような状況を示す。それは、出力が適宜割り当てられるかもしれないという結果になる。この実施形態においては、Ａ０が常に出力に割り当てられる。

この方式を用いると、再並べ替えロジックが迂回され（すなわちｍ＿Ｔａ＝ｍ＿Ｔ０等）、図６におけるブロック４０の入力ですべてのスレッドが何らかの期間に同じメトリックを用いて要求する場合、常に、スレッド０にはアクセスが与えられるであろう。これは、上述の等しい帯域幅割り当て要求を無視する。これが、シフトが必要であり、これらの均衡状態の間はメモリ帯域幅の等しい割り当てが提供されるようにそれが実行される理由である。

図６における最後のハードウェアブロック、すなわちユニット１８が、要求に応じてデータと決定スレッドの制御入力を外部メモリへ接続するために使用される。それは１９におけるデータ入力を受信し、これらを２０における外部メモリへ接続する。これがすべて、そこに到来するスレッド決定４９の制御のもとで、比較器ブロック４０によってなされる。

上記はスレッド優先度を動的に変化させる方法を示す。他のものも明らかに可能である。どんなメトリックであろうとも、これらのメトリックが、個別にまたは他のメトリックとの組合せにおいて、動的な優先度を生成するために使用され得る。例えば、このシステムは、各スレッドのアクセスのための多数のクロック周期においてデッドラインカウントのみを使用する。そういった状況において、与えられるために待っている間に、アクセスがデッドラインに近づくほど、優先度はそのスレッドのためのものより高くなる。すべてのスレッドが実行を完了するための時間を有することを保証するために、スレッドの負荷における変化を反映するようデッドラインの設定をレジスタによって変更することが、もちろんいつでも可能である。

入力ストリームの固定的および動的な優先度アスペクトのユーザ定義の組合せを表す総合的スレッド決定メトリックを生成する説明された方法は、いかなる種類のアービターへも適用することができる。この特定の適用においては、メモリ・プレ・アービターとして示された。この実施は仲裁方式が、ラウンドロビン、ページ内最適化、およびＡＭＡ状態の単独、または多くの柔軟性を与えるすべての３つのスケールまたは混合に基づくことを許容する。

図１は上述のマルチスレッド化されたプロセッサのための典型的なサブモジュールを示す。 図２は本発明を実現するメモリ・プレ・アービターのアーキテクチャを図解的に示す。 図３は本発明の実施形態におけるページ内メトリック生成の実施を図解的に示す。 図４は本発明の実施形態における使用のためのスレッドのためのＡＭＡ抜出ブロックの実施を図解的に示す。 図５は本発明の実施形態におけるスレッドＮのための総合的メトリック生成の実施を示す。 図６は本発明の実施形態における仲裁ブロックを図解的に示す。 図７は本発明の実施形態におけるスレッドメトリックの再並べ替えを示す。

Claims (7)

1. マルチスレッド化されたプロセッサのメモリへのアクセスを動的に割り当てるコンピュータによって実行される方法であって、
   一つより多いスレッドを同時に実行するマルチスレッド化されたプロセッサを構成し、 メモリアクセスを前記一つより多いスレッドから要求し、
   一つまたはそれより多いスレッドの各スレッドのための自動非インターロックパイプラインステージマイクロプロセッサ（ＭＩＰＳ）配置（ＡＭＡ）メトリックを前記各スレッドのための実行メトリックから導出する段階と、
   前記各スレッドのためのページ内メトリックを最後のメモリアクセスのページアドレスおよび実行スレッドのために要求されたページ内アドレスから導出する段階と、
   前記ＡＭＡメトリックおよびページ内メトリックに基づいて前記メモリへのアクセスを決定する段階とを備え、
   前記ページ内メトリックを導出するために、前記最後のメモリアドレスのページアドレスがレジスタ内に格納され、前記実行スレッドのためのページ内アドレスと比較され、
   前記ページ内メトリックはメモリレイテンシを最適化するために使用され、
   ビットスライスを二つの実行メトリックのそれぞれから取得する段階と、前記ＡＭＡメトリックを導出するために前記ビットスライスを組み合わせる段階とによって前記ＡＭＡメトリックが導出されることを特徴とする方法。
2. ビットスライスのための通過手段により、各ビットスライスをレンジ超過確認ロジックに通過させ、ビットスライスがレンジを越えている場合、値を最大に設定する段階を備えることを特徴とする請求項１に記載の方法。
3. 前記ページ内メトリックを各スレッドのためのユーザ定義の優先度と組み合わせる段階を含むことを特徴とする請求項２に記載の方法。
4. 二つまたはそれより多いスレッドから前記リソースへの等しいアクセスに等しい同等のメトリックを与える段階を備えることを特徴とする請求項３に記載の方法。
5. 前記ＡＭＡメトリックが、それまでにスレッドが実行されなければならないデッドラインに基づくものであることを特徴とする請求項１に記載の方法。
6. 前記ＡＭＡメトリックが、スレッドの実行が要求されてからの遅延に基づくものであることを特徴とする請求項１に記載の方法。
7. マルチスレッド化されたプロセッサのメモリへのアクセスを動的に割り当てるためのコンピュータであって、
   一つより多いスレッドを同時に実行するマルチスレッド化されたプロセッサと、
   各スレッドのための自動非インターロックパイプラインステージマイクロプロセッサ（ＭＩＰＳ）配置（ＡＭＡ）メトリックを、そのスレッドのための実行メトリックから導出する手段と、
   各スレッドのためのページ内メトリックを、最後のメモリアクセスのページアドレスと実行スレッドのために要求されるページ内アドレスから導出する手段と、
   前記ＡＭＡメトリックおよびページ内メトリックにしたがって、各スレッドのためのメモリおよびその他のリソースへのアクセスを決定する手段とを備え、
   前記ページ内メトリックを導出するために、前記最後のメモリアドレスのページアドレスがレジスタ内に格納され、前記実行スレッドのためのページ内アドレスと比較され、
   前記ページ内メトリックはメモリレイテンシを最適化するために使用され、
   ビットスライスを二つの実行メトリックのそれぞれから取得する段階と、前記ＡＭＡメトリックを導出するために前記ビットスライスを組み合わせる段階とによって前記ＡＭＡメトリックが導出されることを特徴とするコンピュータ。

Images