(57)【要約】  マルチプロセッサシステムまたはアレイに適した、ハードウェアメモリアーキテクチャまたは配列が提案される。本発明は、機能ユニット（計算ユニット）と、前記機能ユニットが（書き込み、および／または、読み出しのために）アクセスする、少なくとも１つのメモリ装置との間に、少なくとも１つのメモリキューを追加することである。
2008545187.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも２つの機能ユニットと、
少なくとも１つのメモリ装置と、
各機能ユニットに対して少なくとも１つのメモリキューと、
を含むマルチプロセッサシステムであって、
各メモリキューは機能ユニットに関連付けられ、
前記少なくとも１つのメモリ装置は、少なくとも２つのメモリキューに接続される、マルチプロセッサシステム。
【請求項２】
複数のメモリ装置を含み、
各機能ユニットに対するメモリキューの数は、１つ以上、かつ、存在するメモリ装置の数以下であり、
前記マルチプロセッサシステムは、いずれのメモリキュー出力がいずれのメモリ装置へのメモリアクセスを行うかを選択するための、スイッチング手段をさらに含む、
請求項１に記載のマルチプロセッサシステム。
【請求項３】
各メモリ装置に対するメモリキューの数は、１つ以上、かつ、存在する機能ユニットの数以下であり、
前記マルチプロセッサシステムは、いずれのメモリキュー出力が、いずれの機能ユニットにデータを転送するかを選択するための、スイッチング手段をさらに含む、
請求項１または請求項２に記載のマルチプロセッサシステム。
【請求項４】
前記スイッチング手段は、少なくとも１つのマルチプレクサを含む、請求項２または請求項３に記載のマルチプロセッサシステム。
【請求項５】
前記スイッチング手段は、メモリ装置につき１つのマルチプレクサを含む、請求項４に記載のマルチプロセッサシステム。
【請求項６】
メモリ装置の数は、機能ユニットの数の４倍よりも小さい、請求項１から請求項５のいずれか一項に記載のマルチプロセッサシステム。
【請求項７】
メモリ装置は、シングルポートまたはデュアルポートである、請求項１から請求項６のいずれか一項に記載のマルチプロセッサシステム。
【請求項８】
機能ユニットの数は、少なくとも８つである、請求項１から請求項７のいずれか一項に記載のマルチプロセッサシステム。
【請求項９】
機能ユニット当たりのメモリキューの数は、メモリ装置の数に等しい、請求項１から請求項８のいずれか一項に記載のマルチプロセッサシステム。
【請求項１０】
各メモリ装置は、前記機能ユニットのそれぞれの、１つのメモリキューに関連付けられる、請求項９に記載のマルチプロセッサシステム。
【請求項１１】
メモリ装置の数は、２の累乗ではない、請求項１から請求項１０のいずれか一項に記載のマルチプロセッサシステム。
【請求項１２】
機能ユニットとメモリ装置との間に、前記機能ユニットに関連付けられたメモリキューをバイパスするためのバイパス手段をさらに含む、請求項１から請求項１１のいずれか一項に記載のマルチプロセッサシステム。
【請求項１３】
前記少なくとも１つのメモリ装置からのデータの正しい順序を維持するための、リオーダレジスタファイルをさらに含む、請求項１から請求項１２のいずれか一項に記載のマルチプロセッサシステム。
【請求項１４】
メモリアクセスの低記憶コスト表現を記憶するための、追加の記憶ユニットと、いずれのメモリアクセスを処理するかを選択するため、および、前記選択されたメモリアクセスを処理するための制御信号を前記メモリ装置に提供するための、制御手段とをさらに含む、請求項１〜１３のいずれか一項に記載のマルチプロセッサシステム。
【請求項１５】
前記少なくとも１つのメモリ装置は、キャッシュメモリである、請求項１から請求項１４のいずれか一項に記載のマルチプロセッサシステム。
【請求項１６】
ＳＤＲＡＭベースの主メモリをさらに含む、請求項１５に記載のマルチプロセッサシステム。
【請求項１７】
追加のメモリと、前記少なくとも１つのメモリ装置と前記追加のメモリとの間のデータ転送のための、ＤＭＡコントローラとをさらに含む、請求項１から請求項１６のいずれか一項に記載のマルチプロセッサシステム。
【請求項１８】
少なくとも２つの機能ユニットと、各機能ユニットに対して少なくとも１つのメモリキューとを含むディジタルシステムの、少なくとも２つのメモリ装置を含むメモリ配列内の、最適化されたデータ編成を決定する方法であって、
各メモリキューは機能ユニットに関連付けられ、前記メモリ装置のそれぞれは、少なくとも２つのメモリキューに接続され、前記ディジタルシステムはアプリケーションの実行のために構成され、
前記方法は、
前記アプリケーションの表現をロードするステップと、前記表現は、少なくとも、データアクセス命令を含み、
前記メモリ配列と前記機能ユニットとの間での、最適な同時データアクセスが得られるように、アクセスされるデータを前記メモリ装置にわたって分布させるステップと、
を含む方法。
【請求項１９】
前記データは分割され、前記分布させるステップは、前記メモリ装置への前記分割データのさまざまな割り当てについて、最適同時データアクセスコスト関数を評価することによって実行される、請求項１８に記載の方法。
【請求項２０】
前記最適同時データアクセスコストは、少なくとも、メモリ競合の数によって決定される、請求項１９に記載の方法。
【請求項２１】
メモリ配列へのいずれのメモリアクセスが処理されるべきかを決定するための方法であって、
前記メモリ配列は少なくとも２つのメモリ装置を含み、前記メモリ配列は、少なくとも２つの機能ユニットと、各機能ユニットに対して少なくとも１つのメモリキューとを含むディジタルシステムのものであり、ここで、各メモリキューは機能ユニットに関連付けられ、前記メモリ装置のそれぞれは、少なくとも２つのメモリキューに接続され、前記メモリアクセスは、前記メモリキュー内に一時的に記憶され、
前記方法は、
各メモリアクセスの低記憶コスト表現を、記憶ユニット内に記憶するステップと、
メモリ配列へのいずれのメモリアクセスが処理されるべきかを決定するための操作を、前記記憶ユニットに対して実行するステップと、を含む方法。
【請求項２２】
前記記憶ユニットは、ラップアラウンドＦＩＦＯ構成を有する、請求項２１に記載の方法。
【請求項２３】
前記低記憶コスト表現は、１ビットである、請求項２１または請求項２２に記載の方法。
【請求項２４】
前記操作は、
メモリアクセスの前記低記憶コスト表現のうちの少なくとも１つの、前記記憶ユニット内での、前記記憶ユニット内の基準位置に関して相対的な位置を判定するステップと、
前記低記憶コスト表現が前記記憶ユニット内にどれくらいの期間存在しているかを、前記相対位置から判定するステップと、
前記記憶ユニット内に最も長く存在している、前記表現のうちの１つまたは複数を選択するステップと、
前記基準位置を変更するステップと、を含む、
請求項２１から請求項２３のいずれか一項に記載の方法。
【請求項２５】
２つ以上の表現が選択される場合は、ランダムに１つの表現のさらなる選択を実行する、請求項２４に記載の方法。
【請求項２６】
メモリ配列内に少なくとも２つのメモリ装置を含むシステム上で実行されるアプリケーションのコンパイルに適した情報を決定するための方法であって、
前記メモリ配列は、少なくとも２つの機能ユニットと、各機能ユニットに対して少なくとも１つのメモリキューとを含むディジタルシステムのものであり、ここで、各メモリキューは機能ユニットに関連付けられ、前記メモリ装置のそれぞれは、少なくとも２つのメモリキューに接続され、
前記方法は、
前記アプリケーションのソースコード表現をロードするステップと、前記表現は、少なくとも、データアクセス命令を含み、
前記アプリケーションの実行時にいずれのメモリ装置へのデータアクセスが実行されるかを特徴付けるステップと、を含み、
実行されるアプリケーションのコンパイルに適した情報の前記決定は、さまざまなメモリ装置へのデータアクセスが、同じサイクルにおいて、コンパイラによって自由にスケジュールされることを指示するステップを含む方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチプロセッサシステム内での使用に適したメモリ配列に関する。
【背景技術】
【０００２】
高並列アーキテクチャは、計算を並列化することによって高い性能を達成する。計算によっては、メモリからデータを読み出すこと、またはメモリに結果を書き込むことを必要とするため、高並列性は、高データスループットによって支持されなければならない。高データスループットを達成するために、そのようなアーキテクチャのメモリ構成は、複数のデータアクセスを同時にサポートしなければならない。そうでない場合、そのようなアーキテクチャの性能は著しく悪化する。
【０００３】
高メモリ帯域幅を提供するための一方法は、真のマルチポートメモリを設計することである（図１）。これは、各サイクルにおいて、Ｎ個（Ｎ＝ポート数）のデータの読み出しまたは書き込みを、いかなる制約もなく行うことが可能である。ただし、Ｎが２よりも大きい場合、そのようなメモリシステムのコストは法外に高い。ポート数の増加とともに、面積、遅延、および電力は非線形に増加する。実際には、デュアルポートまでのＳＲＡＭのみが、広く使用されている。電力とコストとが重要な設計メトリクスである、埋め込みアプリケーションを対象とする場合、真のマルチポートメモリは実行可能な選択肢ではない。
【０００４】
複数データアクセスを提供するための代替の方法は、複数のシングルポートメモリバンクを集めて、擬似マルチポートシステムを形成することである（図２）。このアプローチは、真のマルチポートアプローチに比較して、はるかに安価であり、かつ、高速である。理想的には、同じサイクルにおけるすべてのデータアクセスが、異なるバンクに進むならば、これは真のマルチポートメモリと同様に動作し、複数のメモリアクセスを同時に提供できる。残念なことに、実際には、複数のメモリアクセスが、同じサイクルにおいて、同じバンクに進む可能性があり、一方、メモリバンクは、１つのサイクルにおいて、１つのメモリ要求を処理することしかできない。システムは、すべてのメモリ要求が処理されるまで待機するために、ストールされなければならない。これは、メモリ競合と呼ばれ、性能を大幅に低下させる可能性がある。
【０００５】
複数バンクメモリ構成に関連する１つの問題は、複数のバンク間で、アドレス空間がどのように分割されるかである。アドレス空間は、バンク間で、複数の大きな部分に分割されてもよく、あるいは、アドレス空間は、バンク間でインターリーブされてもよい。第１の方法は、多くの独立したデータ構造が存在する場合に有効である。これにより、各データ構造は、異なるバンクに割り当てられて、競合せずに同時にアクセスされることが可能となる。第２の方法は、限られたデータ構造しか存在しないが、高い帯域幅の要求がデータ構造内に存在する場合に、うまく機能する。これは、多くのマルチメディアおよび電気通信アプリケーションに当てはまる。したがって、インターリーブド複数バンクメモリが、より多くの場合に使用される。例えば、ＴＩの６４ｘシリーズは、２ポートのデータアクセスを提供するための、８メモリバンクからなる、レベル１データキャッシュを備えている［ＴＩ  Ｉｎｃ．、「ＴＭＳ３２０Ｃ６４ｘ  Ｔｅｃｈｎｉｃａｌ  Ｏｖｅｒｖｉｅｗ」、ｗｗｗ．ｔｉ．ｃｏｍ、２００５］。データポートとメモリバンクとは、８×２のフルクロスバーを介して結合される。データレイアウトを慎重に配置し、８バンクのうちの２つのデータに統計的にアクセスすることによって、メモリ競合の量は、低レベルで制御されることが可能である。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
本明細書で考慮されるシステムにおいては、より高いレベルの並列性を維持するために、一般的なＤＳＰよりもはるかに多くのポートを提供しなければならないため、メモリ競合を低減するという課題はより困難である。例として、８×８配列においては、少なくとも８つのメモリポートを提供する必要がある。ＴＩの６４ｘ  ＤＳＰと同じバンク対ポート比を維持する場合、バンクの数は３２となる。必要とされる３２×８クロスバーのコストおよび消費電力は、ＴＩの６４ｘ  ＤＳＰ内に見出される８×２クロスバーの１６倍となる。したがって、ここで考慮されるシステムのための、より良い方法は、ハードウェアおよび／またはソフトウェア技術を適用することによって、より少数のバンクに基づいてメモリ競合を低減するための、より効率的なソリューションを見出すことである。
【課題を解決するための手段】
【０００７】
本発明の第１の態様において、２００４年９月２８日出願の米国仮特許出願第６０／６１４３７９号明細書に提示されたようなマルチプロセッサシステムまたはアレイに適した、ハードウェアメモリアーキテクチャまたは配列が提案され、前記ハードウェアメモリアーキテクチャまたは配列は、少なくとも１つのメモリキューを含む。
【０００８】
本発明は、機能ユニット（計算ユニット）と、前記機能ユニットがアクセス（書き込み、および／または、読み出し）する、少なくとも１つのメモリとの間に、少なくとも１つのメモリキューを追加することである。
【０００９】
最も基本的な実施形態において、本発明は、少なくとも２つの機能ユニットと、少なくとも１つのメモリ装置と、各機能ユニットに対して少なくとも１つのメモリキューと、を含むマルチプロセッサシステムを提供し、ここで、各メモリキューは機能ユニットに関連付けられ、少なくとも１つのメモリ装置は、少なくとも２つのメモリキューに接続される。
【００１０】
マルチプロセッサシステムは、複数のメモリ装置を含んでもよく、ここで、各機能ユニットに対するメモリキューの数は、１つ以上、かつ、存在するメモリ装置の数以下である。マルチプロセッサシステムは、さらに、いずれのメモリキュー出力がいずれのメモリ装置へのメモリアクセスを行うかを選択するための、スイッチング手段を含んでもよい。
【００１１】
あるいは、またはそれに加えて、本発明の実施形態によるマルチプロセッサシステムは、各メモリ装置に対して、１つ以上、かつ、存在する機能ユニットの数以下の、メモリキューを含んでもよい。この場合、マルチプロセッサシステムは、いずれのメモリキュー出力が、いずれの機能ユニットにデータを転送するかを選択するための、スイッチング手段をさらに含んでもよい。上記の実施形態の両方が組み合わされる場合、メモリ装置に向けてアクセスするためのメモリキューと、メモリ装置からのメモリキューとは、任意選択で、共有されてもよい。
【００１２】
上記のスイッチング手段は、少なくとも１つのマルチプレクサを含んでもよい。スイッチング手段は、メモリ装置につき１つのマルチプレクサを含んでもよい。
【００１３】
好ましい実施形態においては、場合によりアレイ内に配置された、複数の機能ユニット（計算ユニット）と、場合によりバンク構成内に配置された、複数のメモリとを有するマルチプロセッサシステムが提供され、ここで、前記機能ユニットの少なくとも部分に対して、存在するメモリの数と同数のメモリキューが提供され、各機能ユニットの各メモリキューは、前記メモリのうちの１つのための専用である。
【００１４】
別の実施形態では、追加のリオーダレジスタファイルが、前記機能ユニットの少なくとも部分に対して追加される。これらは、少なくとも１つのメモリ装置からのデータの正しい順序を維持するために提供される。
【００１５】
別の実施形態では、例えば、いわゆるスクラッチパッドメモリなどの、追加のメモリが、マルチプロセッサシステムに追加される。
【００１６】
本発明の実施形態においては、メモリ装置の数は、機能ユニットの数の４倍よりも小さくてもよい。
【００１７】
本発明の実施形態においては、メモリ装置は、シングルポートまたはデュアルポートであってもよい。
【００１８】
少なくとも１つのメモリ装置は、キャッシュメモリであってもよい。マルチプロセッサシステムは、ＳＤＲＡＭベースの主メモリをさらに含んでもよい。
【００１９】
本発明の実施形態においては、機能ユニットの数は、少なくとも８つであってもよい。
【００２０】
本発明の実施形態においては、機能ユニット当たりのメモリキューの数は、メモリ装置の数と同じであってもよい。この場合、各メモリ装置は、機能ユニットのそれぞれの、１つのメモリキューに関連付けられてもよい。
【００２１】
本発明の実施形態においては、メモリ装置の数は、２の累乗でなくてもよい。
【００２２】
本発明の実施形態においては、マルチプロセッサシステムは、機能ユニットに関連付けられたメモリキューをバイパスするための、バイパス手段を、機能ユニットとメモリ装置との間にさらに含んでもよい。
【００２３】
本発明の実施形態においては、マルチプロセッサシステムは、メモリアクセスの低記憶コスト表現を記憶するための、スコアボードとも呼ばれる追加の記憶ユニットと、いずれのメモリアクセスを処理するかを選択するため、および、前記選択されたメモリアクセスを処理するための制御信号を前記メモリ装置に提供するための、制御手段とをさらに含んでもよい。
【００２４】
本発明の実施形態によるマルチプロセッサシステムは、追加のメモリと、少なくとも１つのメモリ装置と追加のメモリとの間のデータ転送のための、ＤＭＡコントローラとをさらに含んでもよい。
【００２５】
第２の態様においては、提案されるメモリキューベースのアーキテクチャを含む、マルチプロセッサアーキテクチャの、メモリ帯域幅の問題を解決するための、ソフトウェア技術または方法が示され、特に、データレイアウトの使用が示される。
【００２６】
本発明は、ディジタルシステムのメモリ配列内の、最適化されたデータ編成を決定するための方法を提供する。メモリ配列は、少なくとも２つのメモリ装置を含み、ディジタルシステムは、少なくとも２つの機能ユニットと、各機能ユニットに対して少なくとも１つのメモリキューとを含み、ここで、各メモリキューは機能ユニットに関連付けられ、メモリ装置のそれぞれは、少なくとも２つのメモリキューに接続され、前記ディジタルシステムは、アプリケーションの実行のために構成される。
【００２７】
この方法は、前記アプリケーションの表現をロードするステップと（前記表現は、少なくとも、データアクセス命令を含む）、前記メモリ配列と前記機能ユニットとの間での、最適な同時データアクセスが得られるように、アクセスされるデータを、前記メモリ装置にわたって分布させるステップとを含む。
【００２８】
前記データが分割される実施形態において、前記分布させるステップは、前記メモリ装置への前記分割データのさまざまな割り当てについて、最適同時データアクセスコスト関数を評価することによって実行されてもよい。前記最適同時データアクセスコストは、少なくとも、メモリ競合の数によって決定されてもよい。
【００２９】
本発明は、メモリ配列へのいずれのメモリアクセスが処理されるべきかを決定するための方法をさらに提供する。前記メモリ配列は、少なくとも２つのメモリ装置を含み、前記メモリ配列は、少なくとも２つの機能ユニットと、各機能ユニットに対して少なくとも１つのメモリキューとを含むディジタルシステムのものであり、ここで、各メモリキューは機能ユニットに関連付けられ、メモリ装置のそれぞれは、少なくとも２つのメモリキューに接続され、前記メモリアクセスは、前記メモリキュー内に一時的に記憶される。この方法は、各メモリアクセスの低記憶コスト表現を、記憶ユニットまたはスコアボード内に記憶するステップと、メモリ配列へのいずれのメモリアクセスが処理されるべきかを決定するための操作を、前記記憶ユニットに対して実行するステップとを含む。記憶ユニットは、ラップアラウンドＦＩＦＯ構成（ｗｒａｐｐｅｄ  ａｒｏｕｎｄ  ＦＩＦＯ  ｏｒｇａｎｉｚａｔｉｏｎ）を有してもよい。低記憶コスト表現は、１ビット表現であってもよい。
【００３０】
実行される操作は、メモリアクセスの前記低記憶コスト表現のうちの少なくとも１つの、前記記憶ユニット内での、前記記憶ユニット内の基準位置に関して相対的な位置を判定するステップと、低記憶コスト表現が前記記憶ユニット内にどれくらいの期間存在しているかを、前記相対位置から判定するステップと、前記記憶ユニット内に最も長く存在している、前記表現のうちの１つまたは複数を選択するステップと、前記基準位置を変更するステップとを含んでもよい。２つ以上の表現が選択される場合、この方法は、ランダムに１つの表現のさらなる選択を実行するステップを含んでもよい。
【００３１】
本発明は、システム上で実行されるアプリケーションのコンパイルに適した情報を決定するための方法をさらに提供する。システムは、少なくとも２つの機能ユニットと、少なくとも２つのメモリ装置を有するメモリ配列とを含むディジタルシステムである。メモリ配列内には、各機能ユニットに対して少なくとも１つのメモリキューが提供され、ここで、各メモリキューは機能ユニットに関連付けられ、メモリ装置のそれぞれは、少なくとも２つのメモリキューに接続される。この方法は、前記アプリケーションのソースコード表現をロードするステップと（前記表現は、少なくとも、データアクセス命令を含む）、前記アプリケーションの実行時にいずれのメモリ装置へのデータアクセスが実行されるかを特徴付けるステップとを含む。実行されるアプリケーションのコンパイルに適した情報の決定は、さまざまなメモリ装置へのデータアクセスが、同じサイクルにおいて、コンパイラによって自由にスケジュールされることを指示するステップを含む。
【００３２】
本発明の一実施形態においては、ＳＩＭＤ（単一命令多重データ）技術が、データレイアウトアプローチと組み合わせて（あるいは、またはさらに、２の累乗ではないバンク量と組み合わせて）使用される。
【００３３】
一実施形態においては、スクラッチパッドメモリを活用するための、コンパイラ支援が提供される。
【００３４】
実験結果は、提案されたハードウェア技術のうちの１つまたは複数を、それらのみで、または、提案されたソフトウェア（コンパイラ）技術のうちの１つまたは複数と組み合わせて使用することによって、妥当なコストで、ほとんどのメモリ競合を解消するかまたは低減することが可能であることを示す。
【発明を実施するための最良の形態】
【００３５】
インターリーブド複数バンクメモリ構成の基礎
Ｎ個のバンクからなるメモリ構成を仮定する。各バンクはＭバイト幅である。メモリアクセスのバンク番号は、次の式で計算される。
バンク番号＝（アドレス／Ｍ）％Ｎ
バンク内アドレス＝（アドレス／Ｍ）／Ｎ
【００３６】
通常、ＭおよびＮは両方とも２の累乗である（例えば、Ｍ＝４かつＮ＝８）。したがって、バンク番号およびバンク内アドレスの計算はわずかである。配列ｓｈｏｒｔ  Ｄａｔａ［８］［８］が、Ｍ＝４かつＮ＝８の複数バンクメモリシステムにマッピングされると仮定すると、各要素のバンク番号は、第１要素がバンク０から開始されるとすると、表１に示すようになる。
【００３７】
【表１】
2008545187.tif 000003
【００３８】
典型的ループにおけるメモリアクセス特性
考慮中のアーキテクチャにおいては、主な計算モデルは、ソフトウェアパイプライン方式である。ループのみが、それらの重要性と規則性とのために、配列モードでマッピングされる。ループは、新しいイタレーションが、一定の間隔をあけて開始されることが可能な方法でスケジュールされる。高い並列性を達成するために、異なるイタレーションの実行はオーバラップされる。参照により本明細書に全体を援用されるものとする［ビンフォン・メイ（Ｂｉｎｇｆｅｎｇ  Ｍｅｉ）、サージ・ベルナルド（Ｓｅｒｇｅ  Ｖｅｒｎａｌｄｅ）、ディエデリク・ヴァーケスト（Ｄｉｅｄｅｒｉｋ  Ｖｅｒｋｅｓｔ）、ヒューゴー・デ・マン（Ｈｕｇｏ  Ｄｅ  Ｍａｎ）、ルディ・ローウェレンス（Ｒｕｄｙ  Ｌａｕｗｅｒｅｉｎｓ）著「Ｅｘｐｌｏｉｔｉｎｇ  Ｌｏｏｐ−Ｌｅｖｅｌ  Ｐａｒａｌｌｅｌｉｓｍ  ｏｎ  Ｃｏａｒｓｅ−Ｇｒａｉｎｅｄ  Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ  Ａｒｃｈｉｔｅｃｔｕｒｅｓ  Ｕｓｉｎｇ  Ｍｏｄｕｌｏ  Ｓｃｈｅｄｕｌｉｎｇ」、ＩＥＥ  Ｐｒｏｃｅｅｄｉｎｇｓ  Ｃｏｍｐｕｔｅｒ  ＆  Ｄｉｇｉｔａｌ  Ｔｅｃｈｎｉｑｕｅｓ、第１５０巻、第５号、２００３年９月］を参照されたい。
【００３９】
典型的ループのメモリアクセス特性を理解することが、メモリ帯域幅の問題を解決するための鍵である。典型的なマルチメディアおよび電気通信アプリケーションにおいて発明者らが観察した、いくつかの興味深い事実がある。
【００４０】
第１に、特定のサイクルまたはイタレーションにおいて、限定されたメモリバンクへのバースト要求が存在する場合がある。ただし、サイクルおよびイタレーションにわたっての、各メモリバンクに対する平均メモリ要求は、同じレベルである。例えば、ＩＤＣＴ（逆離散コサイン変換）関数内には、水平ループと垂直ループとがある。入力および出力データの両方が、表１に示す８×８配列に記憶される。水平ループの間、各イタレーションでは、データの行を読み出し、８ポイントＩＤＣＴを行い、同じ方法で書き戻す。垂直ループは、列の読み出しおよび書き込みを行うことを除き、同様に振る舞う。したがって、（図３および図４に示すような）以下のバンクアクセスパターンが得られる。各イタレーションにおいて、各バンクへのバースト要求は異なる。特に、垂直の場合、各イタレーションで、８個のバンクのうちの２個がそれぞれ８回の要求を受け取ってもよく、一方、その他のバンクは何も要求を受け取らない。１つのイタレーションに注目すると、各イタレーションは、メモリ競合のため、少なくとも８サイクルを必要とする。しかし、すべてのイタレーションについての平均メモリ要求を見ると、各バンクは、実際には、イタレーション当たり同じ２回の要求を受け取る。理論的には、これは、メモリの観点からは、インターリーブド８バンク編成が２サイクル／イタレーションを維持できることを意味している。異なるイタレーションにおけるメモリアクセスを組み合わせることによって、メモリバンク競合を解決することが可能である。これは、イタレーションがオーバラップする、考慮中のシステムの計算モデルと完全に一致する。
【００４１】
第２に、メモリを通しての、イタレーション間依存は、典型的なマルチメディアおよび電気通信アプリケーションにおいては、まれである。言い換えると、メモリアクセス動作は、通常、パイプライン化されたループのクリティカルパス内にはない。例えば、図５ａ）および図５ｂ）は、メモリ動作を通してのイタレーション間依存を有する場合と有さない場合の２つのループを示す。第１のループでは、次のイタレーションは前のイタレーションが終了した後にのみ開始できるため、メモリ動作のレイテンシがクリティカルである。メモリ動作に３サイクルを要すると仮定すると、各イタレーションには、少なくとも７サイクルを要する（ａ［ｉ］をロードするために３サイクル、加算のために１サイクル、ａ［ｉ＋１］をストアするために３サイクル）。メモリ動作のレイテンシを２サイクル増加させなければならない技術を用いる場合、各イタレーションには７＋４＝１１サイクルを必要とする。性能のペナルティは、イタレーション当たり４サイクルである。第２のループは、メモリを通したイタレーション間依存を有さない。メモリ動作のレイテンシは、全体的性能に対して、はるかに小さな影響しか及ぼさない。メモリ動作を２サイクル増加させる同じ技術が使用される場合、全体的なオーバヘッドは、１００イタレーションにわたって４サイクルのみ、すなわち、０．０４サイクル／イタレーションである。幸いなことに、本発明で対象となるアプリケーションにおけるほとんどのカーネルは、このタイプに属するか、または、このタイプに変換することが可能である。したがって、本明細書に記載したメモリキュー技術が適用可能である。
【００４２】
第３に、正確なバンク情報は、場合によっては、設計時に知られていない。これは、メモリ競合を回避するようにメモリ動作をスケジュールすることが可能な、コンパイラ単独アプローチの採用を困難にする。理想的には、各メモリアクセスの正確なバンク番号が設計時に知られているならば、実行時に競合が発生しない方法でメモリ動作をスケジュールすることが可能である。残念なことに、多くのカーネルには、これは当てはまらない。図６は、ＭＰＥＧ−２デコーダの動き補償におけるコードの一部を示す。すべてのメモリ動作は、＊（．．．）によって示されている。参照ブロックアドレス（コード内のポインタｓ）は、運動ベクトルから計算される。これは、任意のバンクから開始してもよい。したがって、例えば、＊ａｄｄｒ８＿ｄと＊ａｄｄｒ８＿ｓとの間などの、一部のメモリアクセスの間のバンク関係は、設計時には知られていない。あらゆる状況でバンク競合を回避するような方法で、メモリ動作をスケジュールすることは、不可能である。さらに、ＦＦＴなどの一部のカーネルでは、設計時にすべてのバンク情報が知られているが、メモリアクセス間のバンク競合関係は、イタレーションにわたって変化する。これもまた、コンパイラ単独アプローチの採用を困難にする。これは、考慮されるアーキテクチャ内で使用される、モジュロスケジューリング技術による。この方法では、１つのイタレーションのみがスケジュールされ、イタレーションにわたって繰り返される。２つのメモリ動作が、１つのイタレーション内でメモリ競合を防止することが可能な方法でスケジュールされた場合、イタレーションにわたって変化するバンク関係のため、他のイタレーション内でメモリ競合が発生しないことを保証することはできない。
【００４３】
上記の観察は、さらに説明する提案されるアプローチの基礎を提供する。典型的ループのメモリ特性を利用することにより、メモリ競合を低減するためのハードウェアおよび／またはソフトウェアソリューションを、場合によっては組み合わせて提案する。
【００４４】
メモリキューアーキテクチャ
上記の観察に基づいて、典型的ループのメモリアクセス特性を利用することによりメモリ競合を低減するためのアーキテクチャ、メモリキューを提案する。メモリキューの基本的な考え方は、サイクルおよびイタレーションにわたってバースト要求を平滑化するために、各メモリバンクに対するバッファを提供することである。これは、他のソフトウェア変換技術と組み合わせられることが好ましく、その理由は、それによりメモリ競合が大幅に減少する可能性があるからである。このアプローチのオーバヘッドは、ハードウェアコストの増加と、メモリ動作のレイテンシの増加である。ただし、前節で指摘したように、メモリ動作のレイテンシの増加は、ほとんどのカーネルでは、全体的性能に小さなペナルティを追加するのみである。メモリ競合の減少に比較すると、このオーバヘッドは小さい。
【００４５】
提案されるメモリキューアーキテクチャ
メモリキューを含む本発明の実施形態の概念の一般的構成を、図７に示す。これは、ロード／ストア機能ユニット、キュー、任意選択のスイッチング手段（パラレル−シリアルアービトレータなど）、メモリバンク、および任意選択のリオーダレジスタという、複数のタイプの構成要素を含む。
【００４６】
図８は、メモリ要求のデータフローを示す。フロー全体は、例えば５サイクルの、一定の合計レイテンシを有する。これは、ロード／ストア機能ユニットが、データが５サイクルで到着することを予期するということを意味している。これは、パイプライン化された方法で、数サイクルを要するメモリ動作を実装する、他のプロセッサと同様である。メモリ要求は、最初に、ロード／ストア機能ユニットによって開始される。要求は、ターゲットアドレスと、データ（書き込みの場合）とを含む。次に、これは、キュー内にバッファリングされ、スイッチング手段またはパラレル−シリアルロジックによって選択され、ターゲットメモリバンクに到着する。書き込み要求の場合は、ここで終了する。読み出し要求の場合は、メモリバンクからのデータが、正しい順序を維持するためにリオーダレジスタ内にバッファリングされてもよく、そして、一定のレイテンシの終わりまで待機する。このフローの間、タグが要求に関連付けられてもよい。タグは、一定のレイテンシに初期化され、各サイクルにおいて１だけ減少させられる。基本的に、これは、要求の「緊急度」と、要求が時間どおりに処理されることができない場合にマルチプロセッサアーキテクチャがストールさせられる必要があるかどうかとを反映する情報を提供する。各構成要素の詳細は、以下の文中で説明する。
【００４７】
ロード／ストア機能ユニットとメモリバンクとの間のキューは、メモリ要求のバッファリングおよび平滑化において重要な役割を果たす。各キューは、小さなＦＩＦＯ（先入れ先出し）である。キューのサイズは、わずか１レジスタであってもよい。これらの小さなキューをグループ化するための、多くの方法がある。図９は、ロード／ストア機能ユニットと、接続されたキューとの、次の３つの構成を示す。ａ）１つのキューがすべてのバンクによって共有される、ｂ）複数のキューがすべてのバンクによって共有される、ｃ）各バンクのための専用キュー。
【００４８】
各ロード／ストア機能ユニットに対して１つのみのキューがある場合（図９ａ）、明白な利点は、他の構成に比べてはるかに低いハードウェアコストである。他方、この単純な構成は、いわゆるヘッドオブライン（ＨＯＬ）ブロッキング（図１０）を生成する可能性が非常に高い。１つのサイクルにおいて、ロード／ストア機能ユニットはバンクＡへの要求を発行するが、バンクＡは他の要求処理のために占有されていると仮定する。次のサイクルにおいて、同じロード／ストア機能ユニットは、バンクＢへの別のメモリ要求を発行する。前の要求がまだキューを去っていないため、バンクＢへのメモリ要求は、バンクＢが空いていても、不必要にブロックされる。ブロッキングは、必ずしもストールを引き起こすわけではない。しかし、ブロックされた要求が時間内に処理されない場合、最終的にはストールを引き起こす。それにもかかわらず、アプリケーションの種類によっては、このソリューションが選択されてもよい。
【００４９】
一代替方法は、図９ｂに示すように、各ロード／ストア機能ユニットに対して複数のキューを提供することである。メモリ要求は、ターゲットバンク番号に関係なく、それらのキューのうちの１つによって、より自由にバッファリングされる。この構成では、図９ｃのような各バンクに対する専用キューに比較して、キューリソースはより効率的に使用される。他方、これは、前の要求がブロックされていても、代替のキューに要求がバッファリングされてもよいため、不必要なストールを減少させることが可能である。それにもかかわらず、このアプローチは、やはりいくつかの欠点を有する。第１に、制御ロジックがかなり複雑になる。制御ロジックは、空いているか、または最も少なく占有されるキューを調べてから、そのキューにメモリ要求を送らなければならない。このアービトレーションは、ささいなものではなく、遅延を増加させるか、または追加のサイクルを必要とする。第２に、これは、キューの出力側におけるハードウェアコストを追加する。各キューは任意のメモリバンクへの要求を記憶できるため、それらの要求から選択するために、例えばマルチプレクサなどの、より広い、または追加のレベルのスイッチング手段が必要となる。これは、シリコン面積と、遅延と、消費電力とを増加させる。最後に、これは、ヘッドオブラインブロッキングを完全に解決することはやはりできない（図１１）。それにもかかわらず、アプリケーションの種類によっては、このソリューションが選択されてもよい。
【００５０】
上記の潜在的問題を回避するために、本発明の一実施形態では、ネットワークスイッチングにおける仮想出力キューイング（Ｖｉｒｔｕａｌ  ｏｕｔｐｕｔ  ｑｕｅｕｉｎｇ（ＶＯＱ））［アディサク・メキットクル（Ａｄｉｓａｋ  Ｍｅｋｋｉｔｔｋｕｌ）、ニック・マッコーエン（Ｎｉｃｋ  ＭｃＫｅｏｗｎ）著「Ａ  Ｓｔａｒｖａｔｉｏｎ−ｆｒｅｅ  Ａｌｇｏｒｉｔｈｍ  Ｆｏｒ  Ａｃｈｉｅｖｉｎｇ  １００％  Ｔｈｒｏｕｇｈｐｕｔ  ｉｎ  ａ  Ｉｎｐｕｔ−Ｑｕｅｕｅｄ  Ｓｗｉｔｃｈ」、Ｉｎｔｅｒｎａｔｉｏｎａｌ  ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  ｃｏｍｐｕｔｅｒ  ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ａｎｄ  ｎｅｔｗｏｒｋｓ（ＩＣＣＣＮ）、ワシントンＤＣ（Ｗａｓｈｉｎｇｔｏｎ，ＤＣ）、１９９６年１０月］の概念に類似したキュー編成を採用する。各ロード／ストア機能ユニットは、各バンクのための独立したキューを維持する。利点は多種多様である。第１に、他の２つの構成が有するようなヘッドオブラインブロッキングが存在しない。メモリ要求がブロックされるのは、同じバンクへの以前の要求がまだ処理されていない場合のみである。そのような状況では、ブロッキングは不可避である。第２に、複数のキューを使用する構成に比較して、制御ロジックはより単純である。どのキューを選択するかについての決定を行うことなく、各要求は対応するキュー内に直接バッファリングされてもよい。第３に、キューの出力側も、より単純である。各バンクは、異なるバンクからのキューを多重化するためのマルチプレクサを必要とする。マルチプレクサおよびアービトレーション回路は、複数キュー構成よりも単純である。このアプローチの欠点は、より多くのレジスタを必要とするということである。レジスタの総数は、Ｍ×Ｎ×Ｓとして計算されてもよく、ここで、Ｍはロード／ストア機能ユニットの総数、Ｎはバンクの総数、Ｓはキューのサイズである。
【００５１】
メモリキューは、したがって、バンク競合を発生させる可能性がある、複数のＬＤ／ＳＴ機能ユニットによって生成される要求が、メモリバンクによって処理される方法を制御する。要求の処理は、システム設計者によって設定されてもよい一定のレイテンシを前提とする。メモリ要求は、メモリバンクがそれらを処理する準備ができるまで、キューに入れられてもよい。保留中の要求が、設定されたレイテンシ以内に処理されることができないような長い時間、キュー内で待機する場合、メモリキューは機能ユニットをストールさせる。メモリキューが、保留中の要求のレイテンシを満足する可能性を予測した場合、機能ユニットは再開させられる。
【００５２】
各メモリバンクと、このバンクのためのバッファリングを行うすべてのキューとの間には、マルチプレクサがある。各サイクルにおいて、メモリバンクは１つの要求のみを処理することができるため、複数の要求がキュー内で待機している場合、何らかのアービトレーションアルゴリズムが必要とされる。効果的な基準は、各要求の「緊急度」である。前に示したように、各要求にタグが関連付けられてもよい。タグは、最初に、事前定義されたレイテンシに設定され、各サイクルの後で１だけ減少させられる。これは、ロード／ストア機能ユニットが、タグと同じサイクル数でデータが到着することを予期するということを意味している。明らかに、タグがより小さければ、要求の緊急度はより高い。例えば、図１２では、３つのキューが、異なるタグを有する要求を含んでいる。ロード／ストア機能ユニット２からの要求が、最も急を要するものであるため、選択される。その他のアービトレーションアルゴリズムが可能である。
【００５３】
本発明は、上記のアービトレーションの目的を達成するためのアルゴリズムも提案する。考え方は、メモリ要求の低記憶コスト表現を、スコアボードとも呼ばれる記憶ユニット内に、一時的に記憶するということである。この文脈においては、各要求について１ビットを記憶すれば十分である。スコアボード内での要求の位置は、その要求が受信された時間を決定する。現在の要求が、どれくらいの時間、キュー内に滞在したかを判定するために、カウンタが使用される。このカウンタは、待ち時間カウンタ（ＷＴ）と呼ばれる。これらの２つのタイミング情報は、メモリキューが前に説明したように機能するために十分なものである。
【００５４】
図１９は、４つのＬＤ／ＳＴ機能ユニットに接続されたスコアボードを有するメモリキューの関連部分のブロック図を示す。スコアボードの行は、特定のＬＤ／ＳＴ機能ユニットに関連付けられた要求のタイムラインを表す。そのようなスコアボードの動作は、スコアボードへの書き込みのプロセスと、スコアボードからの読み出しのプロセスという、２つの独立したプロセスとして見られてもよい。
【００５５】
書き込みプロセスの間は、各クロックサイクルにおいて、ＬＤ／ＳＴ機能ユニットからのすべての要求がスコアボード内に新しい列を追加しながら捕らえられ、その列内の各行は特定のＬＤ／ＳＴ機能ユニットを指している。特定のサイクルにおいて、メモリバンクへの書き込み要求が行われない場合、新しい列は空白になることに留意されたい。さらに、スコアボードが空の場合、書き込みプロセスは、メモリバンクが要求処理を即座に行うことができるように、メモリキューをバイパスすることを決定してもよい。機能ユニットのうちの少なくとも１つがストールさせられた場合、この書き込みプロセスは停止する。
【００５６】
読み出しプロセスの間は、各クロックサイクルにおいて、スコアボードの現在の列が、保留中のすべての要求について走査される。同じ列内の要求は、任意の順序で処理されてもよい。所与の列内に保留中の要求がない場合、メモリキューは次の列に進んで、その要求の処理を行う。次の列が空の場合、メモリキューは次の列に進み、以下同様となる。要求が処理された場合、その要求はスコアボードから除去される。列のすべての要求が処理された場合は、列全体がスコアボードから除去される。機能ユニットがストールさせられても、この読み出しプロセスは停止しない。
【００５７】
要求がキュー内に存在した時間の長さを基本的に計算する、待ち時間（ＷＴ）カウンタが提供される。これは、規定されたレイテンシ以内に要求が処理されることができない場合に、機能ユニットをストールさせるために使用される。ＷＴカウンタは、メモリバンクから受信したデータを並べ替えるために必要な情報を渡す。ＷＴカウンタの操作は、コアのステータス（ストール／アクティブ）と、スコアボード内の保留中の要求のレイアウトとに依存する。
【００５８】
そのようなスコアボードの実装には、タグを使用した以前の実装に比べてより少ないシリコン面積を要し、その理由は、すべてのタグが１つのＷＴカウンタによって置き換えられるためである。タグの比較は、保留中の要求についてのスコアボードの検査によって置き換えられ、これによりタイミングが改善される可能性がある。これは、ＬＤ／ＳＴ機能ユニットの数が多い場合に、特に有利である。
【００５９】
書き込みトランザクション、すなわち、メモリバンクまたはメモリ装置内への書き込みについては、メモリ要求がターゲットメモリバンクに到達すると、データフローは終了する。読み出し要求、すなわち、メモリバンクからの読み出しについては、メモリバンクからのデータが、元のロード／ストア機能ユニットにディスパッチされる。ここで１つの問題が発生する可能性がある。２つの読み出し要求ａおよびｂが、同じロード／ストア機能ユニットによって開始され、それらはそれぞれ、バンク０およびバンク１に進んだと仮定する。ａはｂよりも前に開始される。したがって、データａがｂよりも早く到着するのが正しい順序である。しかし、バンク０が他のロード／ストア機能ユニットからの要求の処理を行っているため、ａはキュー内で数サイクルにわたってブロックされ、一方、バンク１は利用可能なため、ｂの処理はただちに行われる場合、実際には、ｂの結果がａの結果よりも早く到着する。これは、メモリキューからの結果は、順序が狂っているということを意味する。さらに、メモリレイテンシは事前定義されており、コンパイラは、所与の、事前定義されたメモリレイテンシに従ってループをスケジュールするため、指定されたレイテンシの終わりまで、データはどこかにバッファリングされなければならない。
【００６０】
上記の問題に対処するための方式を、ここで示す。正しいデータ順序を得るため、および事前定義されたレイテンシの終わりまでデータをバッファリングするために、いくつかのリオーダレジスタファイルが、メモリバンクとロード／ストア機能ユニットとの間に挿入されてもよい。リオーダレジスタの数は、合計レイテンシから、オーバヘッドサイクルを減算した値に等しい。オーバヘッドサイクルは、メモリ要求のキューへの出入り、パラレル−シリアル変換（多重化）、実際のメモリアクセスなどのサイクルを含む。したがって、リオーダレジスタファイルは、到着したデータをバッファリングするための十分な領域を有することが可能である。
【００６１】
リオーダレジスタファイルは、ＦＩＦＯ（先入れ先出し）ではない。これは、１つの入力ポートと１つの出力ポートとを有する。両方のポートのアドレス指定機構を、図１４に示す。モジュロカウンタが、入力および出力の両方のアドレスを生成するために使用される。カウンタは、サイクルごとに更新される。入力ポートアドレスは、タグとカウンタ値との合計であるのに対して、出力ポートアドレスは、カウンタ値のみである。例えば、データａは、サイクルｉにおいて、３のタグとともに到着し、データｂは、サイクルｉ＋１において、１のタグとともに到着する。サイクルｉにおけるカウンタ値が０であると仮定すると、ａはレジスタ３に書き込まれ、ｂはレジスタ２に書き込まれる。出力側では、ｂはサイクルｉ＋２において読み出され、ａはサイクルｉ＋３において読み出される。したがって、間違ったデータ順序が訂正されるだけでなく、両方のデータが正しいタイミングでメモリキューアーキテクチャから出る。
【００６２】
本発明による、メモリ要求をバッファリングするためのメモリキューを使用しても、次の２つの状況において、ストールはやはり発生する可能性がある（図１５）。１）キューがいっぱいで、新しいメモリ要求をバッファリングすることができない、２）要求が、一定のレイテンシ以内に終了できないような長い時間、キュー内で待機する。各ロード／ストア機能ユニットが、各バンクのための専用のキューを有する場合は、非常に小さなキューを使用しても、第１の状況の確率は低い。ロード／ストア機能ユニットが同じバンクに対して繰り返し要求を開始し、以前の要求が時間どおりに処理されない（図１５ａ）、という場合を除き、キューはオーバフローしない。後の状況については、実装によって、異なる位置でストールが調べられてもよい。例えば、メモリバンクおよびリオーダレジスタの両方が１サイクルを要すると仮定すると、キューの先頭における任意の要求のタグが（レイテンシ−２）よりも小さい場合に、ストールがトリガされる。これは、この要求が時間内に処理されることができないことを意味する。したがって、ストールがトリガされる（図１５ｂ）。
【００６３】
メモリキューアーキテクチャをサポートするために、特別なコンパイル技術は必要ない。コンパイラが、複数サイクルのメモリ動作をサポートする限り、メモリキューは正しく扱われることが可能である。
【００６４】
本発明の代替実施形態を、図２０に開示する。この図では、４つのメモリ装置Ｍ１、Ｍ２、Ｍ３、Ｍ４が、メモリキューｑｉｊ、ｉ＝１．．．４、ｊ＝１．．．４、を介して、機能ユニットＦＵ１、ＦＵ２、ＦＵ３、ＦＵ４に結合されている。図示されている実施形態では、各メモリ装置のためのメモリキューの数は、存在する機能ユニットの数（すなわち、４）と同じである。マルチプロセッサシステムは、さらに、いずれのメモリキュー出力がいずれの機能ユニットにデータを転送するかを選択するための、スイッチング手段を含む。図示されている例では、スイッチング手段は、複数のマルチプレクサを含む。
【００６５】
本発明のさらに別の実施形態を、図２１に示す。この図では、４つの機能ユニットＦＵ１、ＦＵ２、ＦＵ３、ＦＵ４と、４つのメモリ装置Ｍ１、Ｍ２、Ｍ３、Ｍ４とが示されている。各機能ユニットについての、４つのメモリキューｑｉｊ、ｉ＝１．．．４、ｊ＝１．．．４と、いずれのメモリキュー出力がいずれのメモリ装置へのメモリアクセスを行うかを選択するための、スイッチング手段、図示されている実施形態では４つのマルチプレクサＭＵＸ１、ＭＵＸ２、ＭＵＸ３、ＭＵＸ４とが提供される。各メモリ装置についての、４つのメモリキューｑｉｊ’、ｉ＝１．．．４、ｊ＝１．．．４と、いずれのメモリキュー出力がいずれの機能ユニットにデータを転送するかを選択するための、スイッチング手段、図示されている実施形態では４つのマルチプレクサＭＵＸ１’、ＭＵＸ２’、ＭＵＸ３’、ＭＵＸ４’とがさらに提供される。
【００６６】
図面に示していない別の実施形態では、メモリキューｑｉｊと、メモリキューｑｉｊ’とは共有されてもよい。
【００６７】
メモリキューの複雑性評価
この節では、メモリキュー実装のハードウェアコストの大まかな見積もりを試みる。ロード／ストア機能ユニットの数＝８、バンク数＝８、キューサイズ＝２、メモリレイテンシ＝５、データ幅＝３２と仮定する。これは、キューレジスタが、８（ロード／ストア機能ユニット）×８（バンク）×２（キューサイズ）×６４（データ＋アドレス）＝８１９２フリップフロップを含むことを意味する。キュー−バンクマルチプレクサの数は、８（バンク）×６４（データ＋アドレス）の８対１マルチプレクサ＝５１２の８対１マルチプレクサである。リオーダレジスタファイルは、８（バンク）×３（レジスタファイルサイズ）×３２（データ）＝７６８フリップフロップと、８（バンク）×３２（データ）＝２５６の３対１マルチプレクサおよび１対３デマルチプレクサとを含む。
【００６８】
その他の、より小さなハードウェアコストおよび制御ロジックは計数されていない。メモリキューは、かなりのハードウェアリソースを使用するが、その活動レベルのため、それほど多くの電力は消費しない。例えば、８（ロード／ストア機能ユニット）×８（バンク）＝６４の小さなキューが存在してもよい。しかし、任意の瞬間には、多くても８個（ロード／ストア機能ユニットの数）のキューが書き込まれる。
【００６９】
実験結果
実験は、メモリキューシミュレータに基づく。これは、異なるレイテンシ、異なるメモリバンク数、異なるキューサイズ、などのメモリキューをシミュレートすることが可能である。
【００７０】
表２は、いくつかの関数の実験結果を示す。最初の４つは、最適化されたＭＰＥＧ−２デコーダからのものである。ＩＤＣＴ＿ａｄｄ＿ｂｌｏｃｋは、ＩＤＣＴ、飽和、およびブロック追加の機能を含む。これは、３つのカーネルからなる。Ｆｏｒｍ＿ｐｒｅｄｉｃａｔｉｏｎｓは、異なる場合の動き補償のための、８つのカーネルを含む。Ｄｅｑｕａｎｔｉｚｅ＿ｉｎｔｒａおよびＤｅｑｕａｎｔｉｚｅ＿ｎｏｎ＿ｉｎｔｒａは、イントラブロックおよび非イントラブロックについての、２つの逆量子化関数である。それぞれは、１つのループからなる。ＦＦＴ＿ｒａｄｉｘ４は、基数４の複素ＦＦＴ（高速フーリエ変換）関数であり、２つのループからなる。実験は、４０９６ポイントのＦＦＴについて実行される。
【００７１】
第２列は、単純な複数バンク編成が使用される場合の、メモリ競合のパーセンテージである。そのようなメモリ編成では、各サイクルにおいて、すべてのメモリ要求が満足されるまで、マルチプロセッサアーキテクチャ全体がストールされなければならない。列３〜５は、いくつかの異なるメモリレイテンシの、メモリ競合およびオーバヘッドのパーセンテージを示す。メモリ競合のパーセンテージは、次の式で定義される。
競合サイクル／（総サイクル−競合サイクル）
【００７２】
オーバヘッドのパーセンテージは、次の式で定義され、ここで、追加サイクルは、正常なメモリ動作のレイテンシを３サイクルと仮定した、メモリキューの使用と不使用との間のサイクル差を示す。
追加サイクル／（総サイクル−競合サイクル）
【００７３】
メモリキューは、単純な複数バンク編成と比較して、メモリ競合を大幅に低減することが可能であることがわかる。５サイクルのレイテンシを使用した場合でも、メモリ競合は５０％〜７０％減少する。キューサイズを増加すれば、メモリ競合はさらに減少するが、ただし、性能オーバヘッドとハードウェアコストとの増加も伴う。一部のカーネルにおいては、オーバヘッドが非常に重要になる。主な理由は、それらのループ内でのイタレーションの数が非常に限られているということである。したがって、メモリレイテンシの増加は十分には隠蔽されない。
【００７４】
【表２】
2008545187.tif 000004
【００７５】
メモリ競合を低減するためのデータレイアウトの変更
メモリキューは、異なるサイクルおよびイタレーションにわたってバンク要求を平滑化することができ、メモリ競合を大幅に低減することができるが、やはり、まず、異なるバンクへのメモリ要求が均等に分布させられることが好ましい。特定のバンクへのバーストメモリ要求が高すぎる場合、要求をバッファリングするために、より長いキューが必要となる。これは、性能オーバヘッドを増加させるだけでなく、より多くのシリコン面積および消費電力も必要とする。
【００７６】
多くのカーネルについては、メモリ要求のバンク分布は、データレイアウトを最適化することによって変更することが可能である。発明者らが適用した主な方法は、各イタレーションにわたってバンクアクセスパターンをシフトさせるということである。例えば、ＩＤＣＴ関数において、８×８配列の代わりに８×９配列を割り当て、しかし、追加の列の要素は計算に使用されないようにすることが可能である。追加の列は、図３に示すように、配列のバンク分布をうまく変更する。
【００７７】
【表３】
2008545187.tif 000005
【００７８】
図１６および図１７は、水平および垂直ループの両方におけるすべてのイタレーションのバンク分布を示す。特に、垂直ループにおける各バンクへの要求が、図４とは対照的に、うまく平滑化されていることがわかる。ほとんどのバンクは、各イタレーションで２つの要求のみを受け取る。したがって、小さなメモリキューでも、容易に扱うことが可能である。
【００７９】
表４は、データレイアウトの最適化がいくつかのベンチマークに適用された後の実験結果を示す。ＩＤＣＴ＿ａｄｄ＿ｂｌｏｃｋとＦｏｒｍ＿ｐｒｅｄｉｃａｔｉｏｎｓとについては、手法は本質的に同じである。２次元配列が、１つの追加の列を使用して割り当てられる。したがって、各イタレーションで使用されるバンク番号はシフトされ、それにより、異なるバンクにわたるバースト要求は、より均等に分布させられる。２つの逆量子化関数に適用される最適化は、単純である。１６ビットタイプのいくつかの変数が、異なるバンクに分布させられるように、３２ビットタイプに置き換えられる。ＩＤＣＴ＿ａｄｄ＿ｂｌｏｃｋについては、ほとんどすべてのメモリ競合が、この単純な変換のみによって解消される。他のベンチマークについても、ハードウェア単独の技法に比較して、競合は大幅に低減される。したがって、提案されるアーキテクチャと組み合わせた、データレイアウト最適化のための体系的なアプローチの使用は、優れた結果を示す。
【００８０】
データレイアウトの最適化は手動で実行されてもよいが、これには、設計者の経験と、設計者によるアプリケーションの理解とが、データを変換するために必要とされる。あるいは、より体系的なアプローチが、ツール内に実装される。別のアプローチは、このステップを自動化することではなく、設計者がバンク情報を洞察するのを助け、データレイアウトの変更方法についてのいくつかの提案を行う、ツールを提供することである。
【００８１】
【表４】
2008545187.tif 000006
【００８２】
メモリ帯域幅要求とメモリ競合とを低減するためのＳＩＭＤの使用
各メモリバンクは、ほとんどの場合に対応するために、通常は３２ビット幅である。しかし、多くのカーネルは、８ビットまたは１６ビットのデータタイプに対して動作し、それらのデータアクセスの多くは、連続したアドレスに対して行われる。これは、貴重なメモリ帯域幅の非効率的な使用をもたらすだけでなく、不必要なメモリバンク競合も発生させる。例えば、ループ内の２つのメモリ読み出し、Ａ［２＊ｉ］およびＡ［２＊ｉ＋１］を考慮すると、これらの２つのアクセスは、同じバンクに進む可能性がある。したがって、それらのアクセスを実行するために２つのメモリ装置が必要とされるだけでなく、それらのアクセスが同じサイクルにおいてスケジュールされる場合、単純な複数バンクシステムでは、ストールサイクルも発生する。この状況はメモリキューによって対処されることが可能ではあるが、ループ内でそのようなケースがあまりにも多く現れる場合は、やはりストールを引き起こす可能性がある。例えば、Ｆｏｒｍ＿ｐｒｅｄｉｃａｔｉｏｎｓ内のカーネルは、多数の連続した８ビットアクセスを含む。入力ブロックへの４アクセスと、参照ブロックへの４アクセスと、出力ブロックへの４アクセスとが、すべて同じバンクに進む可能性がある（図６）。したがって、長いメモリキューを使用する場合でさえ、１回のイタレーション内にあまりにも多くの同一バンクアクセスがあるため、メモリ競合を完全になくすことはやはりできない。この状況は、前述のデータレイアウト変換によって軽減することは不可能である。
【００８３】
この問題を解決するには、他のプロセッサ（Ｉｎｔｅｒ  ｘ８６、ＴＩ  ＤＳＰ、その他）で広く使用されている、ＳＩＭＤ（単一命令多重データ）技術を適用する必要がある。一般に、ＳＩＭＤは、１つの命令が複数の短いデータ項目に対して並列に動作する技術である。本発明では、データアクセス部分にのみＳＩＭＤを適用する。基本的な考え方は、複数の小さな連続したデータ項目を組み合わせて、大きなデータ項目にするということである。これは、１つの命令によって読み出しおよび書き込みされる。大きなデータ項目は、読み出しされた後、通常のｓｈｉｆｔ／ａｎｄ演算によって、または専用のｍｖｈ／ｍｖｌ演算によって、元の小さなデータ項目に分割される。同様に、より小さなデータ項目は、最初にマージされてから、大きなデータ項目としてメモリに書き込まれる。この方法により、メモリ帯域幅がより効率的に使用されるようになるだけでなく、メモリ競合の可能性も減少する。
【００８４】
表５は、単純な複数バンクソリューションと比較した、メモリキューのメモリ競合を示す。Ｆｏｒｍ＿ｐｒｅｄｉｃａｔｉｏｎｓおよびＦＦＴ＿ｒａｄｉｘ４のみに、ＳＩＭＤ変換が適用される。Ｆｏｒｍ＿ｐｒｅｄｉｃａｔｉｏｎｓでは、入力および出力ブロックへの、４バイトのアクセスが組み合わされて、１つの３２ビットアクセスにされる。ただし、参照ブロックへのアクセスは、３２ビット境界に沿っている場合と沿っていない場合とがあるため、組み合わされることができない。ＦＦＴ＿ｒａｄｉｘ４では、２つの１６ビットデータ（複素数の２つの部分）が組み合わされて、１つの３２ビットアクセスにされる。２つの逆量子化ループは、メモリアクセスを組み合わせるためのいかなる可能性も有さない。ＩＤＣＴ＿ａｄｄ＿ｂｌｏｃｋは、非常に低いメモリ競合をすでに有しており、したがってＳＩＭＤ変換は適用されない。
【００８５】
【表５】
2008545187.tif 000007
【００８６】
ＳＩＭＤ変換の後、メモリ競合は、変換なしのバージョンに比較して大幅に減少する。
【００８７】
２の累乗ではないバンク量
２の累乗ではないバンク量は、特定のカーネルに対して、より良好な結果を生成する場合がある。実際には、その効果は、前述のデータレイアウト最適化に非常に類似している。マルチメディアおよび電気通信アプリケーションの多くのアルゴリズムは、２の累乗の倍数のデータセットとアクセスパターンとを有するため（例えば、８×８  ＩＤＣＴ、１０２４ポイントＦＦＴ）、２の累乗ではないメモリバンク量を使用することにより、異なるバンクへのメモリ要求は、より均等に分布させられる。したがって、より短いメモリキューを使用する場合でも、より少ないメモリ競合を予期することができる。次の実験は、ＦＦＴ＿ｒａｄｉｘ４を除き、データレイアウトおよびＳＩＭＤ変換なしで、ベンチマーク上で行われた。
【００８８】
【表６】
2008545187.tif 000008
【００８９】
結果は交錯している。いくつかの、２の累乗ではない値は、８バンクソリューションよりも良好である。例えば、すべての、２の累乗ではない値は、８バンクよりもはるかに良好である。しかし、いくつかの、２の累乗ではない値は、８バンクソリューションよりもさらに悪い（例えば、ＩＤＣＴ＿ａｄｄ＿ｂｌｏｃｋについての、６バンクおよび９バンク）。さまざまなカーネルおよびさまざまなアプリケーションのための、一般的なバンク数を見出すことは困難である。これは、さまざまなアプリケーションの実行を目的とする、再構成可能アーキテクチャについての、アーキテクチャ上の選択を困難にする。第２に、バンク数が２の累乗である場合は、バンク番号とバンク内アドレスとの計算はわずかである。バンク数が２の累乗でない場合、モジュロおよび除算の計算を行うための、追加の回路が必要とされる。さらに、モジュロ計算は、少なくとも１つの追加のサイクルをさらに必要とし、これはメモリキューに加えて、性能オーバヘッドを増加させる。
【００９０】
完全なアプリケーションについての実験結果
完全なアプリケーションへのメモリ競合の影響を理解するために、ＭＰＥＧ−２デコーダ上で、あるシミュレーションを行った。表７にその結果を示す。ＶＬＩＷコードについては、単純な複数バンク編成が使用されると仮定したが、その理由は、より長いレイテンシは、スカラーコードにおいては、はるかに高いオーバヘッドを課すため、メモリ競合が低減されても、発生した性能ペナルティを埋め合わせることはできないからである。その上、サイクル当たりのメモリアクセスは、配列部分ほど多くはない。したがって、単純な複数バンク構成が、メモリ競合を統計的に回避することによって、非常にうまく動作する。
【００９１】
【表７】
2008545187.tif 000009
【００９２】
結果から、単純な複数バンク構成を使用する場合でも、全体的な競合はそれほど大きくはないと考えることができる。これは、マッピングされたＭＰＥＧ−２デコーダでは、配列モードで費やされる時間は半分未満であるためである。したがって、配列モードにおける高いメモリ競合は、全体的性能においてあまり重大であるようには見えない。しかし、アプリケーションが、ＦＦＴ＿ｒａｄｉｘ４のような、よりカーネル主導型のものである場合、メモリ競合は全体的性能に対してはるかに大きな影響を及ぼす。
【００９３】
メモリ帯域幅を増加するためのスクラッチパッドメモリの追加
多くの場合、スクラッチパッドメモリの追加は、メモリ帯域幅を増加するための安価な方法である。例えば、ＩＤＣＴにおいて、小さなバッファが、水平ループと垂直ループとの間の一時データを記憶することができ、それによりメモリ帯域幅は倍になる。同様に、Ｈ．２６４／ＡＶＣデコーダの動き補償とデブロッキングフィルタとにおいても、小さなバッファが、一時データを記憶するために使用されてもよい。
【００９４】
一般的な状況をサポートするための、スイッチング手段とメモリキューとを備えた、主メモリ階層とは異なり、スクラッチパッドメモリは、スイッチング手段とメモリキューとを有さない、はるかに単純なものであってもよい。しかし、これは、データ配列内で高帯域幅を提供するために、やはり、複数バンク構成かつインターリーブドでなければならない。そのようなスクラッチパッドメモリサブシステムは、対象となるアプリケーションによって要求される、より高いメモリ帯域幅を提供するだけでなく、電力も低下させる。その理由は、より小さなスクラッチパッドメモリは、アクセス当たりのエネルギー消費が、主メモリ階層に比較して、一般により少ないためである。
【００９５】
アーキテクチャ上は、これらのスクラッチパッドメモリの追加は困難ではない。重要な問題は、コンパイラ支援を有するということである。その第１の実施形態では、コンパイラは、さまざまなメモリサブシステム上へのマッピングを設計者が手動で開発することを可能にする、インタフェースを提供する。第２の実施形態では、コンパイラは、それらのスクラッチパッドメモリの使用を自動的に引き出すことが可能である。
【００９６】
追加の実施形態
メモリキューはバンク競合を大幅に減少させることが可能であるが、まだ多くの改善の余地がある。同じメモリキューサイズでメモリ競合を低減することが可能であり、あるいは、設計時に既知の情報をコンパイラが利用できる場合は、メモリキューサイズを低減して、同じメモリ競合の量を達成することも可能である。例えば、２つの３２ビットメモリアクセスＡ［ｉ］とＡ［ｉ＋８］とは、８バンクメモリシステムでは、常に同じバンクに進む。一方、Ａ［ｉ］とＡ［ｉ＋１］とは、常に異なるバンク上で発生し、したがって、これらは同じサイクルにおいて自由にスケジュールされることが可能である。コンパイラがこの情報を十分に活用することができる場合、多くの不必要なバッファリングと潜在的なストールとは回避されることが可能であり、また、キューリソースはより効率的に使用されることが可能である。コンパイラは、したがって、ソースコードを解析して情報を取得し、その情報を表現して、その後、その表現をコンパイラに渡すための、プリコンパイラによって補助されなければならず、また、コンパイラは、それらの制約条件をスケジューラ内に組み込むように適合されなければならない。
【００９７】
上記で指摘したように、スクラッチパッドメモリの追加は、メモリ帯域幅を増加し、消費電力を低減するための、安価な方法である。ただし、コンパイラは、スクラッチパッドメモリによるアプローチをサポートしていなければならない。スクラッチパッドメモリサブシステム内でクロスバーが使用されない場合、各ＦＵが付属のメモリバンクのみにアクセスすることを保証するためには、正確なデータ解析および変換技術が不可欠である。実際には、特定のスクラッチパッドメモリシステムへのメモリアクセスを手動で指定するための、組み込み関数を使用することが可能である。組み込み関数は、ＳＩＭＤアクセスおよびその他の特殊命令をサポートするために、本実施形態のコンパイラ内にすでに実装されている。
【００９８】
本明細書では、レベル１メモリの構成のみを説明したことに留意すべきである。レベル１メモリは、ハードウェアベースのキャッシュ、またはソフトウェア制御のキャッシュであってもよい。メモリ階層内に、より多くのレベルを有することが可能である。通常は、ＳＤＲＡＭベースの主メモリが存在すべきである。レベル１メモリとその他のレベルとの間のデータ転送は、一般に、ＤＭＡコントローラを介して実行される。
【図面の簡単な説明】
【００９９】
【図１】（従来技術）アレイ内に配置された複数の機能ユニット（ＦＵ）（一部のユニットはレジスタファイル（ＲＦ）と結合されている）を使用し、クロスバーに接続されたマルチポートメモリ構成を有し、一部の機能ユニットは、アレイの他の部分のための、ロード／ストア機能ユニットとして機能する、マルチプロセッサシステムを示す。
【図２】（従来技術）複数バンクシングルポートメモリシステムを使用する、図１におけるマルチプロセッサシステムに類似したマルチプロセッサシステムを示す。
【図３】逆離散コサイン変換（ＩＤＣＴ）水平ループのバンクアクセスパターンを示す。
【図４】ＩＤＣＴ垂直ループのバンクアクセスパターンを示す。
【図５】ａ）メモリを通したイタレーション間依存を有するループ。ｂ）メモリを通したイタレーション間依存を有さないループ。
【図６】ＭＰＥＧ−２における動き補償を示す。
【図７】機能ユニットからメモリ装置へのデータ転送のための、少なくとも１つのメモリキューを含む、本発明のメモリアーキテクチャを示す。
【図８】発明されたメモリキューアーキテクチャの、データフローを示す。
【図９】ロード／ストア機能ユニットと、接続されたキューとの、３つの構成を示す。ａ）１つのキューがすべてのバンクによって共有される。ｂ）複数のキューのそれぞれがすべてのバンクによって共有される。ｃ）各バンクに対する専用のキュー。
【図１０】図９ａの構成で起こりうる影響を示す。
【図１１】図９ｂの構成で起こりうる影響を示す。
【図１２】複数のキュー（それぞれが機能ユニット（図示せず）に結合されている）をバンクに接続するために使用される、キュー−バンクマルチプレクサを示す。
【図１３】リオーダレジスタファイルが使用される、本発明のさらなる実施形態を示す。
【図１４】リオーダレジスタファイルのためのアドレス指定方式を示す。
【図１５】２つのストール状況を示す。ａ）キューオーバフローストール。ｂ）要求が時間内に処理されることができない。
【図１６】ＩＤＣＴ水平ループのバンクアクセスパターンを示す。
【図１７】ＩＤＣＴ垂直ループのバンクアクセスパターンを示す。
【図１８】メモリ帯域幅を増加するためにスクラッチパッドメモリサブシステムが追加された、さらなる実施形態を示す。
【図１９】４つの機能ユニットに接続されたスコアボードを有する、本発明の一実施形態によるメモリキューの関連部分のブロック図である。
【図２０】メモリ装置から機能ユニットへのデータ転送のための、少なくとも１つのメモリキューをマルチプロセッサシステムが含む、本発明の一実施形態のブロック図である。
【図２１】機能ユニットからメモリ装置へのデータ転送のためのメモリキューと、メモリ装置から機能ユニットへのデータ転送のためのメモリキューとを、マルチプロセッサシステムが含む、本発明の一実施形態のブロック図である。
【図１】
2008545187.tif 000010
【図２】
2008545187.tif 000011
【図３】
2008545187.tif 000012
【図４】
2008545187.tif 000013
【図５】
2008545187.tif 000014
【図６】
2008545187.tif 000015
【図７】
2008545187.tif 000016
【図８】
2008545187.tif 000017
【図９】
2008545187.tif 000018
【図１０】
2008545187.tif 000019
【図１１】
2008545187.tif 000020
【図１２】
2008545187.tif 000021
【図１３】
2008545187.tif 000022
【図１４】
2008545187.tif 000023
【図１５】
2008545187.tif 000024
【図１６】
2008545187.tif 000025
【図１７】
2008545187.tif 000026
【図１８】
2008545187.tif 000027
【図１９】
2008545187.tif 000028
【図２０】
2008545187.tif 000029
【図２１】
2008545187.tif 000030
【国際調査報告】
2008545187.tif 000031
2008545187.tif 000032
2008545187.tif 000033
2008545187.tif 000034
2008545187.tif 000035