(57)【要約】  デコードされたベクトルデータアクセス命令に応答してデータ記憶装置内に格納されたデータにアクセスするためのベクトルデータアクセスユニットが開示される。ベクトルデータアクセス命令のそれぞれは、実行されるデータアクセスを示す複数の要素を含む。なおこれらの要素は、対応するデータアクセスが実行されるよう命令されるベクトルデータアクセス命令内で１つの順序に並ぶ。少なくとも２つのベクトルデータアクセス命令のそれぞれについて、複数の要素内の要素の位置から、複数の要素により示される複数のデータアクセスのうちのいずれがベクトルデータアクセス命令に対して実行される次のデータアクセスであるかを判定し、データアクセスは命令された順序で実行されることと、ベクトルデータアクセス命令のそれぞれについて、次のデータアクセスを示す要素を判定することと、ベクトルデータアクセス命令のうちの後の方の複数の要素内の次のデータアクセスを示す要素の数値位置と、前の方のベクトルアクセスデータ命令の複数の要素内の次のデータアクセスを示す要素の数値位置と、の間の差異が所定値よりも小さいという制約の支配下で、少なくとも２つのベクトルデータ命令が受け取られた順序と、それぞれの複数の要素内で互いに対する次のデータアクセスを示す要素の位置と、に応じて、データ格納器に発行される次のデータアクセスとして次のデータアクセスのうちの１つを選択することと、を行うために、ベクトルデータアクセスユニットは、要素により示されたデータアクセス要求をデータ格納器に発行するためのデータアクセス順序付け回路を備える。データアクセス順序付け回路は、少なくとも２つのデコードされたベクトルデータアクセス命令を受け取ることに応答して構成され、少なくとも２つのデコードされたベクトルデータアクセス命令の前の方は少なくとも２つのデコードされたベクトル命令の後の方よりも前に受け取られ、少なくとも２つのデコードされたベクトルデータアクセス命令のうちの一方は書き込み命令であり、少なくとも２つのデコードされたベクトルデータアクセス命令からのデータアクセスが限定的な程度までインターリービングされることができることを示す。
2014532221.tif 000002
【特許請求の範囲】
【請求項１】
デコードされたベクトルデータアクセス命令に応答してデータ記憶装置内に格納されたデータにアクセスするためのベクトルデータアクセスユニットであって、前記ベクトルデータアクセス命令のそれぞれは複数の要素を特定し、前記要素のそれぞれは実行されるデータアクセスを示し、前記複数の要素は、前記対応するデータアクセスが、
前記少なくとも２つのベクトルデータアクセス命令のそれぞれ対して、前記複数の要素内の前記要素の位置から、前記複数の要素により示される前記複数のデータアクセスのうちのいずれが前記ベクトルデータアクセス命令に対して実行される次のデータアクセスであるかを判定し、前記データアクセスは前記命令された順序で実行されることと、
前記ベクトルデータアクセス命令のそれぞれについて、前記次のデータアクセスを示す要素を判定することと、
前記ベクトルデータアクセス命令のうちの後の方の前記複数の要素内の前記次のデータアクセスを示す前記要素の数値位置と、前の方のベクトルアクセスデータ命令の前記複数の要素内の前記次のデータアクセスを示す前記要素の数値位置と、の間の差異が所定値よりも小さいという制約の支配下で、前記少なくとも２つのベクトルデータ命令が受け取られた順序と、それぞれの複数の要素内で互いに対する前記次のデータアクセスを示す前記要素の前記位置と、に応じて、前記データ格納器に発行される次のデータアクセスとして前記次のデータアクセスのうちの１つを選択することと、
を行う、前記要素により示されたデータアクセス要求を前記データ格納器に発行するためのデータアクセス順序付け回路を備える前記ベクトルデータアクセスユニットであって、前記データアクセス順序付け回路は、少なくとも２つのデコードされたベクトルデータアクセス命令を受け取ることに応答して構成され、前記少なくとも２つのデコードされたベクトルデータアクセス命令の前の方は前記少なくとも２つのデコードされたベクトル命令の後の方よりも前に受け取られ、前記少なくとも２つのデコードされたベクトルデータアクセス命令のうちの一方は書き込み命令であり、前記少なくとも２つのデコードされたベクトルデータアクセス命令からのデータアクセスが限定的な程度までインターリービングされることができることを示す、前記ベクトルデータアクセスユニット、
において実行されるよう命令される前記ベクトルデータアクセス命令内で１つの順序に並ぶ、ベクトルデータアクセスユニット。
【請求項２】
前記制約は、前記前の方のベクトルデータアクセス命令からの要素により示されるデータアクセス要求が、前記後の方のベクトルデータアクセス命令における前記複数の要素の対応する位置に配置された要素により示されるデータアクセス要求の後に発行されないこと、をさらに含む、請求項１に記載のベクトルデータアクセスユニット。
【請求項３】
前記データアクセス順序付け回路は、前記制約が満足される場合、前記前の方のベクトルデータアクセス命令からの前記次のデータアクセス要求に優先して、前記後の方のベクトルデータアクセス命令からの前記発行される次のデータアクセス要求を、前記発行される次のデータアクセス要求として選択するよう構成される、請求項１および請求項２のいずれか１つに記載のベクトルデータアクセスユニット。
【請求項４】
前記データアクセス順序付け回路は、同一のクロックサイクルにおいて互いに並列して少なくとも２つのデータアクセス要求を発行するよう構成され、
前記データアクセス順序付け回路は、前記次のアクセスと、並列して発行するための少なくとも１つのさらなるデータアクセスと、を選択するよう構成され、前記少なくとも１つのデータアクセス要求は、
前記ベクトルデータアクセス命令において前記次のアクセスを示す前記要素に後続する要素により示される少なくとも１つのデータアクセスと、
前記次のアクセスを示す前記要素を含まない前記ベクトルデータアクセス命令のうちの１つからの前記次のアクセスのうちの少なくとも１つと、
のうちの少なくとも１つであり、
前記少なくとも１つのさらなるデータアクセスは、前記次のデータが選択されるのと同一の制約に応じて選択される、
請求項１から請求項３のいずれか１つに記載のベクトルデータアクセスユニット。
【請求項５】
アクセスされる前記データ格納器は複数のバンクメモリのうちの１つのバンクを含む、請求項１から請求項４のいずれか１つに記載のベクトルデータアクセスユニット。
【請求項６】
前記データ格納器は複数バンクのメモリを含み、各バンクは他のバンクから独立的であり、前記データアクセス順序付け回路は、前記少なくとも１つのさらなるデータアクセスを選択するとき、異なるバンクに対するものである同一のクロックサイクルにおいて選択されるアクセスの間のアクセスに前記制約を課さないよう構成される、請求項４に記載のベクトルデータアクセスユニット。
【請求項７】
それぞれが前記少なくとも２つのベクトルデータアクセス命令のうちのそれぞれ１つを受け取るよう構成された、互いに対して並列に配列された少なくとも２つのベクトルデータアクセスモジュールを備える、請求項１から請求項６のいずれか１つに記載のベクトルデータアクセスユニットであって、
前記それぞれのベクトルデータアクセス命令の前記次のデータアクセスを示す前記要素の前記位置の指示を格納するための前記ベクトルデータアクセスモジュールのそれぞれにおけるカウンタと、
前記カウンタの値を比較するための比較回路と、
前記次のデータアクセス要求を発行するための前記ベクトルデータアクセスモジュールのそれぞれに関連付けられた発行回路と、
備え、
前記データアクセス回路は、前記次のデータアクセス要求が発行されると前記制約が満足されないことを示す前記比較回路に応答して、前記モジュールによる前記次のデータアクセス要求の発行を妨げる信号を、前記ベクトルデータアクセスモジュールのうちの一方の前記発行回路に送信するよう構成される、
ベクトルデータアクセスユニット。
【請求項８】
それぞれが前記少なくとも２つのベクトルデータアクセス命令のうちのそれぞれ１つを受け取るよう構成された、互いに対して並列に配列された少なくとも２つのベクトルデータアクセスモジュールを備え、前記データ格納器は複数のキャッシュラインを備えるキャッシュを備え、前記キャッシュラインのそれぞれは複数のデータ項目を格納し、前記データアクセス順序付け回路は、
同一のクロックサイクルにおいて実行される前記ベクトルデータアクセスモジュールからのデータアクセス要求が同一のキャッシュラインに対するものであるかどうかを判定するための検出回路であって、それらが同一のデータアクセスとして実行されるようそれらが前記データアクセスを組み合わせていることを判定することに応答する検出回路、
を備える、請求項１から請求項６のいずれか１つに記載のベクトルデータアクセスユニット。
【請求項９】
前記少なくとも２つのベクトルデータアクセス命令は、ベクトルロード命令およびベクトル格納命令のうちの少なくとも２つを含み、前記ベクトルデータアクセスユニットは、
それぞれが複数のベクトルオペランドを含む、複数のベクトルを格納するためのベクトルレジスタ格納器であって、前記ベクトルのうちの少なくとも２つは、前記少なくとも２つのベクトルデータアクセス命令のそれぞれ１つにより示される前記複数のデータアクセスのデータ格納器位置を示す複数のアドレスを含む、ベクトルレジスタ格納器、
をさらに備える、請求項１から請求項８のいずれか１つに記載のベクトルデータアクセスユニット。
【請求項１０】
データを処理するためのデータ処理装置であって、
処理される命令をフェッチするためのフェッチ回路と、
前記命令をデコードするためのデコード回路と、
前記デコードされた命令に応答して演算を実行するよう構成された処理回路と、
ベクトルデータアクセス命令に応答して処理される前記データにアクセスするための、請求項１から請求項９に記載の前記ベクトルデータアクセスユニットと、
を備える、データ処理装置。
【請求項１１】
請求項１０に記載のデータ処理装置であって、
限定的インターリービングが可能であり、その結果、前記前の方のベクトルデータアクセス命令からのおよび後の方のベクトルデータアクセス命令からのデータアクセスが限定的な程度までインターリービングされるという指示が前記ベクトルデータアクセスユニットに提供されることを示す命令に応答して、前記デコード回路は構成される、
データ処理装置。
【請求項１２】
限定的インターリービングが可能であることを示す前記命令は、ベクトルロード命令、ベクトル格納命令、限定的インターリービングスタート命令、限定的インターリービングフラグを設定するための命令、およびベクトル制御レジスタを設定するための命令のうちの少なくとも１つを含む、請求項１０または請求項１１に記載のデータ処理装置。
【請求項１３】
限定的インターリービングが可能であることを示す前記命令は、前記限定的インターリービングスタート命令を含み、前記限定的インターリービングスタート命令はインターリービングの程度を示す前記所定値を含む、請求項１２に記載のデータ処理装置。
【請求項１４】
限定的インターリービングがもはや許可されず、その結果、ベクトルデータアクセス命令からのデータアクセスが限定的な程度までインターリービングされることができないという指示が前記ベクトルデータアクセスユニットに提供されることを示す命令に応答して、前記デコード回路は構成される、請求項１１に記載のデータ処理装置。
【請求項１５】
限定的インターリービングがもはや可能ではないことを示す前記命令は前記限定的インターリービングストップ命令およびバックワード分岐命令のうちの少なくとも１つを含む、請求項１４に記載のデータ処理装置。
【請求項１６】
前記前の方のベクトルデータアクセス命令からのおよび前記後の方のベクトルデータアクセス命令からのデータアクセスが限定的な程度までインターリービングされることができることを示すフラグ値を格納するためのフラグデータ格納器をさらに備え、前記ベクトルデータアクセスユニットは前記フラグ値を検出するための検出器を備える、請求項１０から請求項１５のいずれか１つに記載のデータ処理装置。
【請求項１７】
前記データ処理装置は、前記フラグ値をクリアするために例外を取ることに応答して構成される、請求項１６に記載のデータ処理装置。
【請求項１８】
コンピュータプログラムをコンパイルする方法であって、
前記コンピュータプログラムを分析し、前記コンピュータプログラム内のループを特定し、前記ループ内のスカラー命令をベクトル命令に変換することであって、前記ベクトル命令はベクトルデータアクセス命令を含み、前記ベクトルデータアクセス命令のそれぞれは複数の要素を特定し、前記要素のそれぞれは実行されるデータアクセスを示すことと、
第１ベクトルデータアクセス命令および第２ベクトルデータアクセス命令からのデータアクセスの限定的インターリービングがデータエラーを生じさせない場合に、前記プログラム内における前記第１ベクトルデータアクセス命令および前記第２データベクトル命令を特定することと、
前記第１ベクトルデータアクセス命令の前に、前記第１ベクトルデータアクセス命令および前記第２ベクトルデータアクセス命令からのデータアクセスが限定的な程度までインターリービングされることができるという指示をベクトルデータアクセスユニットに提供する限定的インターリービングスタート命令を前記コンピュータプログラムに挿入し、
前記限定的な程度は、前記第２ベクトルデータアクセス命令の前記複数の要素内の前記要素の数値位置から前記第１データアクセス命令の次のデータアクセスを示す前記要素の数値位置を減算した値が所定値より小さい場合には、前記第２ベクトルデータアクセス命令からの要素により示される次のデータアクセスが発行され、係る減算した値が前記所定値よりも小さくない場合には、前記第１第１ベクトルデータアクセス命令からのデータアクセスが発行されることであることと、
前記コンピュータプログラムを、データ処理システム上での実行に好適なコードに変換することと、
を含む方法。
【請求項１９】
請求項１８に記載のコンピュータプログラムをコンパイルする方法であって、前記コンピュータプログラム内のループを特定することと、前記ループ内のスカラー命令をベクトル命令に変換することと、の最初の分析ステップを含む、方法。
【請求項２０】
前記限定的インターリービングスタート命令は前記所定値を含む、請求項１８または請求項１９に記載のコンピュータプログラムをコンパイルする方法。
【請求項２１】
前記第１ベクトルデータアクセス命令および第２ベクトルデータアクセス命令を特定する前記ステップは、少なくとも１つのさらなるベクトルデータアクセス命令を、前記第１、第２、および少なくとも１つのさらなるベクトルデータアクセス命令からのデータアクセスの限定的インターリービングがデータエラーを生じさせない場合に、特定することを含み、
前記限定的な程度は、前記後の方のベクトルデータアクセス命令の前記複数の要素内の前記要素の数値位置から前記前の方のデータアクセス命令のうちの１つの次のデータアクセスを示す前記要素の数値位置を減算した値が所定値より小さい場合には、前記コンピュータプログラムコードにおいて後に生じる前記特定されたベクトルデータアクセス命令のうちの１つからの要素により示される次のデータアクセスが発行され、前記減算した値が前記所定値よりも小さくない場合には、前記前の方のベクトルデータアクセス命令からのデータアクセスが発行されることである、
請求項１８から請求項２０のいずれか１つに記載のコンピュータプログラムをコンパイルする方法。
【請求項２２】
前記特定されたベクトルデータアクセス命令の後に限定的インターリービングストップ命令を挿入するステップをさらに含む、請求項１８から請求項２１のいずれか１つに記載のコンピュータプログラムをコンパイルする方法。
【請求項２３】
前記命令を分析し、前記コンピュータプログラム内のバックワード分岐を特定し、前記バックワード分岐が前記インターリービング領域の終点において配置される場合には、インターリービングスタート命令のみを挿入し、インターリービングストップ命令は挿入しないステップをさらに含む、請求項１８から請求項２２のいずれか１つに記載のコンピュータプログラムをコンパイルする方法。
【請求項２４】
コンピュータプログラムをコンパイルするためのコンパイラであって、前記コンピュータプログラムを分析し、前記コンピュータプログラム内のループを特定し、前記ループ内のスカラー命令をベクトル命令に変換するための分析回路であって、前記ベクトル命令はベクトルデータアクセス命令を含み、前記ベクトルデータアクセス命令のそれぞれは複数の要素を特定し、前記要素のそれぞれは実行されるデータアクセスを示し、前記第１ベクトルデータアクセス命令からのおよび第２ベクトルデータアクセス命令からのデータアクセスの限定的インターリービングがデータエラーを生じさせない場合には、第１ベクトルデータアクセス命令および第２データベクトル命令を前記プログラム内で特定するための分析回路と、
限定的インターリービングスタート命令を生成し、前記第１ベクトルデータアクセス命令の前に前記限定的インターリービングスタート命令を前記コンピュータプログラムに挿入するための命令生成回路であって、前記限定的インターリービングスタート命令は、前記第１ベクトルデータアクセス命令および前記第２ベクトルデータアクセス命令からのデータアクセスが限定的な程度までインターリービングされることができるという指示をベクトルデータアクセスユニットに提供し、
前記限定的な程度は、前記第２ベクトルデータアクセス命令の前記複数の要素内の前記要素の数値位置から前記第１データアクセス命令の次のデータアクセスを示す前記要素の数値位置を減算した値が所定値より小さい場合には、前記第２ベクトルデータアクセス命令からの要素により示される次のデータアクセスが発行され、係る減算した値が前記所定値よりも小さくない場合には、前記第１第１ベクトルデータアクセス命令からのデータアクセスが発行されることである、
命令生成回路と、
前記コンピュータプログラムを、データ処理システム上での実行に好適なコードに変換するための変換回路と、
を含む、コンパイラ。
【請求項２５】
少なくとも２つのベクトルデータアクセス命令と、前記ベクトルデータアクセス命令により特定されるデータアクセスが何らかの程度までインターリービングされることができるという指示と、に応答して、データ格納器にデータアクセス要求を発行する方法であって、前記ベクトルデータアクセス命令のそれぞれは、実行される複数の順次てきなデータアクセスをリストし、
前記少なくとも２つのベクトルデータアクセス命令のそれぞれについて、前記複数の順次てきなデータアクセスのうちのいずれが実行される次のデータアクセスであるかを判定するステップと、
前記実行される次のデータアクセスのそれぞれについて、前記他の次のデータアクセスに対する、前記ベクトルデータアクセス命令における前記複数の順次てきなデータアクセスの前記リスト内の前記次のデータアクセスの相対的位置を判定するステップと、
前記前の方のベクトルデータアクセス命令および後の方のベクトルデータアクセス命令のうちの前の方からのデータアクセスが、前記前の方のベクトルデータアクセス命令および後の方のベクトルデータアクセス命令のうちの後の方の順次てきなアクセスの前記リストにおける対応する位置におけるアクセスの後で発行されないよう、前記相対的位置に応じて前記少なくとも２つのベクトルデータアクセス命令のいずれかから前記発行される次のデータアクセスのうちの１つを前記データ格納器に対する次のアクセスとして選択するステップと、
を含む、方法。
【請求項２６】
限定的インターリービングスタート命令と後続の第１ベクトルデータアクセス命令および第２ベクトルデータアクセス命令とを含むコンピュータプログラムを非一時的な形態に格納するコンピュータプログラム製品であって、前記限定的インターリービングスタート命令は、データプロセッサにより実行されると、前記第１および第２後続のベクトルデータアクセス命令により特定されるデータアクセスの限定的インターリービング命令をスタートするよう前記前記データプロセッサを制御し、その結果、前記第１および第２ベクトルデータアクセス命令に応答して実行されるアクセスは限定的な程度までインターリービングされることができ、
前記限定的な程度は、前記第２ベクトルデータアクセス命令の前記複数の要素内の前記要素の数値位置から前記第１データアクセス命令の次のデータアクセスを示す前記要素の数値位置を減算した値が所定値より小さい場合には、前記第２ベクトルデータアクセス命令からの要素により示される次のデータアクセスが発行され、前記減算した値が前記所定値よりも小さくない場合には、前記第１第１ベクトルデータアクセス命令からのデータアクセスが発行されることである、
コンピュータプログラム製品。
【請求項２７】
請求項１０から請求項１７のいずれか１つに記載のデータ処理装置に対応するプログラム命令のための仮想機械実行環境を提供するようコンピュータを制御するコンピュータプログラムを非一時的な形態に格納するコンピュータプログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ処理の分野に関し、さらに詳細には、複数のデータ格納器位置をアクセスするためのベクトル命令に関する。
【背景技術】
【０００２】
データ処理装置の性能を改善するための１つの既知の技術はベクトル演算の実行をサポートする回路を提供することである。ベクトル演算は少なくとも１つのベクトルオペランドに対して実行され、ここで各ベクトルオペランドは複数のオペランド要素を含む。ベクトル演算の実行はベクトルオペランド（単数または複数）内の様々なオペランド要素にわたって反復的に演算を適用することを含む。
【０００３】
ベクトル演算の実行をサポートする通常のデータ処理システムでは、ベクトルレジスタバンクがベクトルオペランドを格納するために提供されるであろう。したがって、例えば、ベクトルレジスタバンク内の各ベクトルレジスタは複数のオペランド要素を含むベクトルオペランドを格納し得る。
【０００４】
高性能の実装では、必要とされるベクトル演算を、ベクトルオペランド内の様々なオペランド要素に対して並行的に実行できるベクトル処理回路（しばしばＳＩＭＤ（Ｓｉｎｇｌｅ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ｄａｔａ）処理回路と呼称される）を提供することが周知である。代替的な実施形態において、スカラー処理回路もベクトル演算の実行に用いることはできるが、この場合では、ベクトル演算は、各反復が異なるベクトルオペランドのオペランド要素に対して実行される状態で、スカラー処理回路を通して演算を反復的に実行することにより実装される。いくつかのベクトル要素が一緒に処理され得る中間的実装が存在することに注意すべきである。
【０００５】
ベクトルデータアクセス命令はそれぞれ複数のデータアクセスを命令する。一般に、処理装置はベクトルアクセス命令により指定されるデータアクセスの全部を、単一サイクル内で互いに並行して、必ずしも実行できるとはかぎらない。アクセスは一般に数サイクルを必要とする。複数のベクトルデータアクセス命令が実行される場合、アクセス速度は、異なるベクトルデータアクセス命令からのデータアクセスが互いに対してインターリービングされるならば、増加され得る。これは、関連するアドレスに対する演算を合併する機会（この機会は係るインターリービングにより導入されるものである）と、使い的な並列性を見出す可能性と、に起因するものである。
【０００６】
いくつかの場合では、実行されるアクセスは互いに対して完全に独立的であり、それらのアクセスの間のインターリービングが可能となり、その結果、アクセスの速度が増加され得る。他の場合では、アクセスが互いに対して独立的ではなく、したがって命令ストリームの順序で実行するよう制約され得る。
【０００７】
図１は、先行技術に係る、アドレスａ０〜ａ７にアクセするためのベクトルアクセス命令と、それに引き続きアドレスｂ０〜ｂ７にアクセスするためのベクトルアクセス命令と、を示す。インターリービングが許可されず２つのデータアクセス要求が１クロックサイクル内で発行され得るシステムにおいてこれらの命令が処理される場合では、データアクセス要求ｂ７は命令が受け取られて７クロックサイクル後に発行されるであろう。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
スカラー演算もサポートするデータ処理装置内でのベクトル演算の実行をサポートするための改善された技術を提供することが望まれるであろう。
【課題を解決するための手段】
【０００９】
第１の態様から観ると、本発明は、デコードされたベクトルデータアクセス命令に応答して、データ格納器内に格納されたデータにアクセスするためのベクトルデータアクセスユニットを提供する。前記ベクトルデータアクセス命令のそれぞれは複数の要素を特定し、前記要素のそれぞれは実行されるデータアクセスを示し、前記複数の要素は、前記対応するデータアクセスが、前記要素により示されるデータアクセス要求を前記データ格納器に発行するためのデータアクセス順序付け回路を備える、前記少なくとも２つのベクトルデータアクセス命令のそれぞれについて、前記複数の要素内の前記要素の位置から、前記複数の要素により示される前記複数のデータアクセスのうちのいずれが前記ベクトルデータアクセス命令に対して実行される次のデータアクセスであるかを判定し、前記データアクセスは前記命令された順序で実行されることと、前記ベクトルデータアクセス命令のそれぞれについて、前記次のデータアクセスを示す要素を判定することと、前記ベクトルデータアクセス命令のうちの後の方の前記複数の要素内の前記次のデータアクセスを示す前記要素の数値位置と、前の方のベクトルアクセスデータ命令の前記複数の要素内の前記次のデータアクセスを示す前記要素の数値位置と、の間の差異が所定値よりも小さいという制約の支配下で、前記少なくとも２つのベクトルデータ命令が受け取られた順序と、それぞれの複数の要素内で互いに対する前記次のデータアクセスを示す前記要素の前記位置と、に応じて、前記データ格納器に発行される次のデータアクセスとして前記次のデータアクセスのうちの１つを選択することと、を行うための、前記ベクトルデータアクセスユニット内で実行されるという前記ベクトルデータアクセス命令内で１つの順序に並ぶ。前記データアクセス順序付け回路は、少なくとも２つのデコードされたデータアクセス命令を受け取ることに応答して構成され、前記少なくとも２つのデコードされたベクトルデータアクセス命令のうちの前の方は前記少なくとも２つのデコードされたベクトル命令の後の方の前に受け取られ、前記少なくとも２つのデコードされたベクトルデータアクセス命令のうちの１つは書き込み命令であり、前記少なくとも２つのデコードされたベクトルデータアクセス命令からのデータアクセスが限定的な程度までインターリービングされることができることを示す。
【００１０】
本発明は、実行される複数のデータアクセスを特定するベクトル命令が、実行するにあたり数サイクルを必要とし得ることを、および異なるベクトル命令内のアクセスのインターリービングが実行できるならば有利であることを、認識する。例えば、一般に、格納の前にロードを実行することは有利である。なぜなら、プロセッサは、多くの場合、後続の動作が実行可能となる前に、ロードの実行を必要とするためである。したがって、ロードのレイテンシを低減することは、多くの場合、格納のレイテンシを低減することよりも、性能に対して大きい影響を及ぼすであろう。
【００１１】
一方、命令をインターリービングする前に、インターリービングの実行が安全であるかどうかを知る必要がある。これは、一般に、同一のアドレスが順序変更されるアクセス要求のいずれによってもアクセスされないことをチェックするために、実行されるアクセスのアドレス比較を必要とする。アドレスは一般にかなり長く、したがって、これらのアドレス比較は実行するにあたりコストが大きくなってしまう。さらに、ベクトル演算に対するアドレス比較の個数は大きくなる。なぜなら、単一のベクトルメモリ演算は、８つの異なるアドレスを用い得るためである。したがって、４つのベクトルメモリアクセスをバッファリング／順序変更する能力を有するベクトルロード／格納ユニットは３２のアドレスをバッファリング／順序変更することが必要となるであろう。本発明は、通常は安全確保のために必要となる多数のアドレス比較を実行することなく、ベクトルメモリアクセスの顕著な順序変更が可能であり得ることを認識する。特に、本発明は、正しくベクトル化されたループではデータアクセスにはＲＡＷ（書き込み後の読み出し）およびＷＡＷ（書き込み後の書き込み）の危険因子が存在せず、したがって、データアクセスの安全なインターリービングを可能とするために実行する必要があるのはアドレス比較の１部分のみであることを認識する。
【００１２】
したがって、本発明は、前記ベクトルデータアクセス命令のうちの後の方の前記複数の要素内の次の前記データアクセスを示す前記要素の数値位置と、前の方のベクトルアクセスデータ命令の前記複数の要素内の前記次のデータアクセスを示す前記要素の数値位置と、の間の差異が所定値よりも小さいならば、換言すると、後の方のベクトルデータアクセス命令からのアクセスの進行が前の方のベクトルデータアクセス命令の進行により制約されるならば、インターリービングを可能にする。知る必要があるのはこれら２つの数値位置の相対値であることが注意されるべきであり、これは減算により、または任意の他の比較手段により、判定されこることができる。
【００１３】
いくつかの実施形態において、前記制約は、前記前の方のベクトルデータアクセス命令からの要素により示されるデータアクセス要求が、前記後の方のベクトルデータアクセス命令における前記複数の要素の対応する位置に配置された要素により示されるデータアクセス要求の後に発行されないこと、をさらに含む。
【００１４】
この制約は、後の方のベクトルデータアクセス命令が、現在のところ実際上、前の方のベクトルデータアクセス命令を部分的に追い越すことができること、であってもよい。これは、１つの命令により命令された、いくつかの要素アクセスが、後続の命令により命令された要素アクセスの前に、または係る要素アクセスと並列して、実行され得ることを意味する。
【００１５】
いくつかの実施形態において、前記データアクセス順序付け回路は、前記制約が満足される場合、前記前の方のベクトルデータアクセス命令からの前記次のデータアクセス要求に優先して、前記後の方のベクトルデータアクセス命令からの前記発行される次のデータアクセス要求を、前記発行される次のデータアクセス要求として選択するよう構成される。
【００１６】
その制約が満足される場合、順序付け回路は、前の方の命令からのデータアクセス要求に優先して、後の方の命令からのデータアクセス要求を選択し得る。これは、危険因子を生じさせることなく、インターリービングを増加させる。
【００１７】
いくつかの実施形態において、前記データアクセス順序付け回路は、同一のクロックサイクルにおいて互いに並列して少なくとも２つのデータアクセス要求を発行するよう構成される。前記データアクセス順序付け回路は、並列して発行するために、前記次のアクセスと少なくとも１つのさらなるデータアクセスを選択するよう構成され、前記少なくとも１つのさらなるデータアクセス要求は、
前記ベクトルデータアクセス命令において前記次のアクセスを示す前記要素に後続する要素により示される少なくとも１つのデータアクセスと、
前記次のアクセスを示す前記要素を含まない前記ベクトルデータアクセス命令の１つからの前記次のアクセスのうちの少なくとも１つと、
のうちの少なくとも１つであり、
前記少なくとも１つのさらなるデータアクセスは、前記次のデータが選択されるのと同一の制約に応じて選択される。
【００１８】
データアクセス要求が並列して選択されることができる場合、同一の制約が、発行される２つのデータアクセス要求を選択するために用いられることができる。
【００１９】
いくつかの実施形態において、アクセスされる前記データ格納器は、複数のバンクメモリのうちの１つのバンクを含む。
【００２０】
データ格納器は複数のバンクメモリのうちの１つのバンクであり得る。係る場合において、メモリ内のバンクは、それぞれがそれぞれの制約を有する個々の独立的な格納ユニットとして取り扱われることができる。そのことが成り立つ場合、メモリアクセスは並列して進行することができ、その結果、アクセスを異なるバンクへと分割および再組み合わせすることのオーバーヘッドは確かに生じるが、処理能力の向上が可能となる。したがって、いくつかの実施形態において、複数のバンクメモリを単一のデータ格納器として取り扱うことは有利であり得るが、一方で他の実施形態においては、各バンクが独立的に取り扱われる。
【００２１】
上述のように、いくつかの実施形態において、前記データ格納器は複数バンクのメモリを含み、各バンクは他のバンクから独立的であり、前記データアクセス順序付け回路は、前記少なくとも１つのさらなるデータアクセスを選択するとき、異なるバンクに対するものである同一のクロックサイクルにおいて選択されるアクセスの間のアクセスに前記制約を課さないよう構成される。
【００２２】
バンクを独立的に取り扱う場合は、制約は同一のバンクへのアクセスに対しては依然として課されるが、異なるバンクの間のアクセスに対する制約は課されない。
【００２３】
いくつかの実施形態において、ベクトルデータアクセスユニットは、それぞれが前記少なくとも２つのベクトルデータアクセス命令のうちのそれぞれの１つを受け取るよう構成された、互いに対して並列に配列された少なくとも２つのベクトルデータアクセスモジュールを備える。なお、前記データアクセス順序付け回路は、
前記それぞれのベクトルデータアクセス命令の前記次のデータアクセスを示す前記要素の前記位置の表示を格納するための前記ベクトルでたあるモジュールのそれぞれにおけるカウンタと、
前記カウンタの値を比較するための比較回路と、
前記次のデータアクセス要求を発行するための前記ベクトルデータアクセスモジュールのそれぞれに関連付けられた発行回路と、
を備える。
なお、前記データアクセス回路は、前記次のデータアクセス要求が発行されると前記制約が満足されないことを示す前記比較回路に応答して、前記モジュールによる前記次のデータアクセス要求の発行を妨げる信号を、前記ベクトルデータアクセスモジュールのうちの一方の前記発行回路に送信するよう構成される。
【００２４】
並列して配列されたベクトルデータアクセスモジュールが存在する場合には、それぞれのベクトルデータアクセスモジュールは、ベクトル内の次のデータアクセスの要素の位置を示すカウンタと、これらのカウンタを比較するための比較回路と、を有し得る。発行される次のデータアクセス要求は、比較の結果に応じて発行される。これにより、要求される制約が満足されることが保証される。
【００２５】
いくつかの実施形態において、ベクトルデータアクセスユニットは、それぞれが前記少なくとも２つのベクトルデータアクセス命令のうちのそれぞれの１つを受け取るよう構成された、互いに対して並列に配列された少なくとも２つのベクトルデータアクセスモジュールを備える。なお、前記データ格納器は複数のキャッシュライン備えるキャッシュを備え、前記キャッシュラインのそれぞれは複数のデータ項目を格納し、前記データアクセス順序付け回路は、
同一のクロックサイクルにおいて実行される前記ベクトルデータアクセスモジュールからのデータアクセス要求が同一のキャッシュラインに対するものであり、それらが同一のデータアクセスとして実行されるようそれらが前記データアクセスを組み合わせることを判定することに応答するものであるかどうかを判定するための検出回路を備える。
【００２６】
キャッシュをアクセスするときに同一のキャッシュラインが異なるベクトルデータアクセスモジュールからのアクセス要求によりアクセスされるかどうかを判定する検出回路を有することは有利となるであろう。アクセスを有る程度までインターリービングする能力は、プログラムストリーム内で互いに近接して生じ、且つ組み合わされる同一のキャッシュラインに対するものである、いくつかのアクセス要求を許可し得る。キャッシュにアクセスすることは電力の面でコストが大きく、同一のキャッシュラインが２つのデータアクセス要求によりアクセスされるとき、これらのアクセスが組み合わされて単一のアクセスが形成されるならば、有利となるであろう。いくつかのアクセスパターンにおいては、キャッシュラインが後続のアクセス要求によりアクセスされ、それにより、アクセス要求をインターリービングする能力が、同一のキャッシュラインに対するアクセスを検出する検出回路と組み合わされて、いくつかの事例において、効率における顕著な改善を提供する可能性がある。
【００２７】
いくつかの実施形態において、前記少なくとも２つのベクトルデータアクセス命令は、ベクトルロード命令およびベクトル格納命令のうちの少なくとも２つを含み、前記ベクトルデータアクセスユニットは、
それぞれが複数のベクトルオペランドを含む、複数のベクトルを格納するためのベクトルレジスタ格納器であって、前記ベクトルのうちの少なくとも２つは、前記少なくとも２つのベクトルデータアクセス命令のそれぞれの１つにより示される前記複数のデータアクセスのデータ格納器位置を示す複数のアドレスを含む、ベクトルレジスタ格納器をさらに備える。
【００２８】
本発明の第２の態様は、処理される命令をフェッチするためのフェッチ回路と、前記命令をデコードするためのデコード回路と、前記デコードされた命令に応答して演算を実行するよう構成された処理回路と、ベクトルデータアクセス命令に応答して処理される前記データにアクセスするための本発明の第１の態様に係る前記ベクトルデータアクセスユニットと、を備えるデータを処理するためのデータ処理装置を提供する。
【００２９】
いくつかの実施形態において、限定的インターリービングが可能であり前記前の方のベクトルデータアクセス命令からのデータアクセスおよび後の方のベクトルデータアクセス命令からのデータアクセスがある程度までインターリービングされることができるという前記指示が、前記ベクトルデータアクセスユニットに提供されることを指示する命令に応答するよう、前記デコード回路は構成される。
【００３０】
限定的インターリービングがどこで可能であるかを示す命令に応答するよう構成されたデコード回路を有することは有利であろう。係る命令を有するならば、ベクトルデータアクセスユニットは、要素位置を比較するべきかどうかを、および制約が満足されるかどうかを、知ることができる。インターリービングが許可されない場合、係る比較は不必要であり、まったく利点がない。インターリービングが適切である命令ストリームの部分も存在し得、インターリービングが不適切である命令ストリームの部分も存在し得る。したがって、この命令は特に有利となることができる。
【００３１】
いくつかの実施形態において、限定的インターリービングが可能であることを示す前記命令は、ベクトルロード命令、ベクトル格納命令、限定的インターリービングスタート命令、限定的インターリービングフラグを設定するための命令、およびベクトル制御レジスタを設定するための命令のうちの少なくとも１つを含む。
【００３２】
限定的インターリービングを指示する命令は、これを示す特定的な命令であってもよく、またはそれは、ベクトルロード命令またはベクトル格納命令などの命令であってもよい。ベクトルロードおよびベクトル格納は、常にインターリービングされることができ、したがって、これらのうちの１つを検出することは、インターリービングが可能であり得ることを十分に示し得る。代替的に、いくつかの実施形態において、これを示す設定されるフラグが存在し、したがって、このフラグを設定するための、またはベクトル制御レジスタを設定するための命令は、インターリービングが現在可能であることを示す命令であり得る。
【００３３】
いくつかの実施形態において、限定的インターリービングが可能であることを示す前記命令は、前記限定的インターリービングスタート命令を含み、前記限定的インターリービングスタート命令はインターリービングの程度を示す前記所定値を含む。
【００３４】
限定的インターリービングが可能であることを示す命令が限定的インターリービングスタート命令である場合、この命令はインターリービングの程度を示す所定値を含み得る。命令ストリームのある区域は特定量のインターリービングを可能にする一方で、他の区域は異なる量を可能にし得るため、これは有用であり得る。命令内に所定値を有することは、異なる量のインターリービングがコードの異なる区域に対して実行されることを許可する。
【００３５】
いくつかの実施形態において、限定的インターリービングが、ベクトルデータアクセス命令からのデータアクセスが限定的程度までインターリービングされることができないという指示を、前記ベクトルデータアクセスユニットに提供ために許可されない指示する命令に応答するよう、前記デコード回路は構成される。
【００３６】
限定的インターリービングがもはや許可されないこと、および要素位置の比較がもはや適切ではないことを示す命令も存在し得る。
【００３７】
この命令は限定的インターリービングストップ命令であってもよく、またはそれはバックワード分岐命令であってもよい。
【００３８】
バックワード分岐命令は、インターリービングが不適切である場合にコードの１部分が入力されることを示す。したがって、このことが認識されると、さらなるインターリービングストップ命令を有する必要はない。
【００３９】
いくつかの実施形態において、データ処理装置はフラグデータ格納器をさらに備える。フラグデータ格納器は、前記前の方のベクトルデータアクセス命令および後の方のベクトルデータアクセス命令からのデータアクセスが限定的な程度までインターリービングされることができることを示すフラグ値を格納するためのものである。前記ベクトルデータアクセスユニットは前記フラグ値を検出するための検出器を備える。
【００４０】
上述のように、データアクセスがインターリービングされることができることを示すフラグ値を有することは適切であり得る。
【００４１】
係る場合、例外はこのフラグ値をクリアし得る。なぜなら、例外はコードの異なる部分が取られることを示すためである。コードのこの異なる部分においてデータアクセスをインターリービングすることはもはや不適切である場合もある。したがって、例外を取るとフラグをクリアすることは、演算が安全性を保持することを可能にするであろう。
【００４２】
本発明の第３の態様は、コンピュータプログラムをコンパイルする方法であって、
前記コンピュータプログラムを分析し、前記コンピュータプログラム内のループを特定し、前記ループ内のスカラー命令をベクトル命令に変換することであって、前記ベクトル命令はベクトルデータアクセス命令を含み、前記ベクトルデータアクセス命令のそれぞれは複数の要素を特定し、前記要素のそれぞれは実行されるデータアクセスを示すことと、
第１ベクトルデータアクセス命令および第２ベクトルデータアクセス命令からのデータアクセスの限定的インターリービングがデータエラーを生じさせない場合に、前記プログラム内における前記第１ベクトルデータアクセス命令および前記第２データベクトル命令を特定することと、
前記第１ベクトルデータアクセス命令の前に、前記第１ベクトルデータアクセス命令および前記第２ベクトルデータアクセス命令からのデータアクセスが限定的な程度までインターリービングされることができるという指示をベクトルデータアクセスユニットに提供する限定的インターリービングスタート命令を前記コンピュータプログラムに挿入することであって、
前記限定的な程度は、前記第２ベクトルデータアクセス命令の前記複数の要素内の前記要素の数値位置から前記第１データアクセス命令の次のデータアクセスを示す前記要素の数値位置から減算した値が所定値より小さい場合には、前記第２ベクトルデータアクセス命令からの要素により示される次のデータアクセスが発行され、係る減算した値が前記所定値よりも小さくない場合には、前記第１第１ベクトルデータアクセス命令からのデータアクセスが発行されることであることと、
前記コンピュータプログラムを、データ処理システム上での実行に好適なコードに変換することと、
を含む方法を提供する。
【００４３】
インターリービングが可能であるという指示はコンパイル段階でコードに挿入され得る。この段階で、コードは分析され、インターリービングが適切であることか判定され得る。係る場合において、コンパイラは、限定的インターリービングが実行できることをプロセッサに示すためにコードに挿入されることができる限定的インターリービングスタート命令を生成し得る。
【００４４】
いくつかの実施形態において、前記限定的インターリービングスタート命令は前記所定値を含む。
【００４５】
安全であるインターリービングの量はコードに依存し、したがって、コンパイラが、可能であるインターリービングの程度の指示を限定的インターリービングスタート命令に挿入することは適切であり得る。
【００４６】
いくつかの実施形態において、前記コンパイルの方法は、前記特定されたベクトルデータアクセス命令の後に限定的インターリービングストップ命令を挿入するステップをさらに含む。
【００４７】
コードをコンパイルするときのインターリービングスタート命令に関しては、インターリービングが適切である場所を判定し、必要に応じてストップ命令を挿入してもよい。
【００４８】
インターリービングされることができる第１ベクトルデータアクセス命令および第２ベクトルデータアクセス命令が１つのループ内にある場合、インターリービングスタート命令およびインターリービングストップ命令は、いくつかの場所に配置され得る。例えば、インターリービングスタート命令はループの前に、またはループ内に生成され得、インターリービングストップ命令はループ内またはループ外に生成され得る。
【００４９】
バックワード分岐がコンピュータプログラム内で特定される他の実施形態において、インターリービングをストップするべきであることを示すために、これらは処理システムにより理解され得る。その場合においてのみ、インターリービングスタート命令はコードに挿入され、バックワード分岐が前記インターリービング領域の終点において配置されるならばインターリービングストップ命令は挿入されない。
【００５０】
本発明の第４の態様によれば、コンピュータプログラムをコンパイルするためのコンパイラが提供される。このコンパイラは、前記コンピュータプログラムを分析し、前記コンピュータプログラム内のループを特定し、前記ループ内のスカラー命令をベクトル命令に変換するための分析回路を備える。なお前記ベクトル命令はベクトルデータアクセス命令を備え、前記ベクトルデータアクセス命令のそれぞれは複数の要素を特定し、前記要素のそれぞれは実行されるデータアクセスを示す。分析回路は、前記第１ベクトルデータアクセス命令からのおよび第２ベクトルデータアクセス命令からのデータアクセスの限定的インターリービングがデータエラーを生じさせない場合、前記プログラム内における第１ベクトルデータアクセス命令および第２データベクトル命令を特定する。このコンパイラは、限定的インターリービングスタート命令を生成し、前記第１ベクトルデータアクセス命令の前に前記限定的インターリービングスタート命令を前記コンピュータプログラムに挿入するための命令生成回路であって、前記限定的インターリービングスタート命令は、前記第１ベクトルデータアクセス命令および前記第２ベクトルデータアクセス命令からのデータアクセスが限定的な程度までインターリービングされることができるという指示をベクトルデータアクセスユニットに提供する、命令生成回路をさらに備える。なお、前記限定的な程度は、前記第２ベクトルデータアクセス命令の前記複数の要素内の前記要素の数値位置から前記第１データアクセス命令の次のデータアクセスを示す前記要素の数値位置を減算した値が所定値より小さい場合には、前記第２ベクトルデータアクセス命令からの要素により示される次のデータアクセスが発行され、係る減算した値が前記所定値よりも小さくない場合には、前記第１第１ベクトルデータアクセス命令からのデータアクセスが発行されることである。このコンパイラは、前記コンピュータプログラムを、データ処理システム上での実行に好適なコードに変換するための変換回路をさらに備える。
【００５１】
本発明の第５の態様によれば、少なくとも２つのベクトルデータアクセス命令と、前記ベクトルデータアクセス命令により特定されるデータアクセスが何らかの程度までインターリービングされることができるという指示と、に応答して、データ格納器にデータアクセス要求を発行する方法であって、前記ベクトルデータアクセス命令のそれぞれは、実行される複数の順次てきなデータアクセスをリストする方法が提供される。なお、この方法は、前記少なくとも２つのベクトルデータアクセス命令のそれぞれについて、前記複数の順次てきなデータアクセスのうちのいずれが実行される次のデータアクセスであるかを判定するステップと、前記実行される次のデータアクセスのそれぞれについて、前記他の次のデータアクセスに対する、前記ベクトルデータアクセス命令における前記複数の順次てきなデータアクセスの前記リスト内の前記次のデータアクセスの相対的位置を判定するステップと、前記前の方のベクトルデータアクセス命令および後の方のベクトルデータアクセス命令のうちの前の方からのデータアクセスが、前記前の方のベクトルデータアクセス命令および後の方のベクトルデータアクセス命令のうちの後の方の順次てきなアクセスの前記リストにおける対応する位置におけるアクセスの後で発行されないよう、前記相対的位置に応じて前記少なくとも２つのベクトルデータアクセス命令のいずれかから前記発行される次のデータアクセスのうちの１つを前記データ格納器に対する次のアクセスとして選択するステップと、を含む。
【００５２】
本発明の第６の態様によれば、限定的インターリービングスタート命令と後続の第１ベクトルデータアクセス命令および第２ベクトルデータアクセス命令とを含むコンピュータプログラムを非一時的な形態に格納するコンピュータプログラム製品であって、前記限定的インターリービングスタート命令は、データプロセッサにより実行されると、前記第１および第２後続のベクトルデータアクセス命令により特定されるデータアクセスの限定的インターリービング命令をスタートするよう前記前記データプロセッサを制御し、その結果、前記第１および第２ベクトルデータアクセス命令に応答して実行されるアクセスは限定的な程度までインターリービングされることができコンピュータプログラム製品が提供される。なお、前記限定的な程度は、前記第２ベクトルデータアクセス命令の前記複数の要素内の前記要素の数値位置から前記第１データアクセス命令の次のデータアクセスを示す前記要素の数値位置を減算した値が所定値より小さい場合には、前記第２ベクトルデータアクセス命令からの要素により示される次のデータアクセスが発行され、前記減算した値が前記所定値よりも小さくない場合には、前記第１第１ベクトルデータアクセス命令からのデータアクセスが発行されることである。
【００５３】
本発明の第７の態様によれば、本発明の第１の態様に係るデータ処理装置に対応するプログラム命令のための仮想機械実行環境を提供するようコンピュータを制御するコンピュータプログラムを非一時的な形態に格納するコンピュータプログラム製品が提供される。
【００５４】
本発明の、上述した、および他の、目的、特徴、および利点は、添付の図面と合わせて読まれるべき、例示的な実施形態に関する以下の詳細な説明から明らかになることであろう。
【図面の簡単な説明】
【００５５】
【図１】インターリービングが許可されないデュアルイシュー・プロセッサにおける２つのベクトル命令のデータアクセスに対するタイミングを示す図である。
【図２】本発明の１つの実施形態に係るデータ処理装置の１部分を示す図である。
【図３】本発明の１つの実施形態に係るベクトルロード格納ユニットを示す図である。
【図４】複数のメモリバンクに格納されたデータにアクセスするための、本発明の１つの実施形態に係る多重ベクトルロード／格納ユニットを示す図である。
【図５】本発明の１つの実施形態に係る、複数のメモリバンクにアクセスするための多重ベクトルロード格納ユニットを示す図である。
【図６Ａ】本発明の１つの実施形態に係るプログラムをコンパイルする方法におけるステップを示す図である。
【図６Ｂ】本発明の１つの実施形態に係るコンパイラを示す図である。
【図７】本発明の１つの実施形態に係るいくつかのキャッシュアクセスの合体を可能にする多重ベクトル格納ユニットを示す図である。
【図８Ａ】合体が行われる図７の多重ベクトルロード格納ユニットからのデータアクセスを示す図である。
【図８Ｂ】合体が命令間でおよび命令内で起こるデータアクセスを示す図である。
【図９Ａ】安全に、または非安全にインターリービングされた図１に示すベクトルアクセス命令を示す図である。
【図９Ｂ】安全に、または非安全にインターリービングされた図１に示すベクトルアクセス命令を示す図である。
【図９Ｃ】安全に、または非安全にインターリービングされた図１に示すベクトルアクセス命令を示す図である。
【図１０】図１に示すベクトルアクセス命令の合体されたアクセスパターンを示す図である。
【図１１】さらに合体されたアクセスパターンを示す図である。
【図１２】バンクされたアクセスパターンを示す図である。
【図１３】さらにバンクされたアクセスパターンを示す図である。
【図１４】非安全なバンクされたアクセスパターンを示す図である。
【図１５】安全なインターリービングされたバンクされたアクセスパターンを示す図である。
【図１６】本発明の１つの実施形態に係る仮想機械実装を示す図である。
【発明を実施するための形態】
【００５６】
図２は本発明の１つの実施形態に係るデータ処理装置５の１部分を示す。図２はベクトル処理部分のみを示し、ベクトル命令およびスカラー命令の両方がデコードおよび実行が可能となるよう、スカラー処理回路、スカラーロード／格納ユニット、およびスカラーレジスタバンクも存在し得る。
【００５７】
この装置において、処理される命令を保持する命令キュー３０と、これらの命令をデコードするデコード回路４０と、デコード回路４０によりデコードされたベクトル命令を処理するためのベクトル処理回路５０と、が存在する。この実施形態には、ベクトル処理回路のための制御値を格納するベクトル制御レジスタ６０も存在する。これらの制御値は、ベクトル命令が特定のベクトルオペランドにのみ適用されることを可能にするために用いられるマスクの形であってもよく、またはベクトル処理を制御するための他の制御値であり得る。
【００５８】
この実施形態では、ベクトルデータアクセス命令を受け取り、これらのアクセス命令に応答してメモリシステムへのアクセスを実行するためのベクトルロード格納ユニット１０も存在する。ベクトル命令の処理において用いられるベクトルを格納するためのベクトルレジスタバンク７０も存在する。
【００５９】
したがって、例えばベクトルデータアクセス命令がデコードされる場合、これは、アクセスされる複数のアドレスを参照し、これらはベクトルレジスタバンク７０内のベクトルに格納され得る。同様に、複数のアドレスに対応する複数のデータ要素もベクトルレジスタバンク７０内のベクトルに格納されるであろう。
【００６０】
この実施形態には、アクセスがある程度まで互いに対してインターリービングされ得るベクトルデータアクセス命令の検出に応答してベクトル処理回路により設定されるフラグ８０も存在する。したがって、処理が行われる間、係る命令が検出された場合はフラグが設定され、係る命令がベクトルロード格納ユニット１０により実行され、インターリービングを許可しないその他の命令が処理される場合は、フラグはクリアされる。このように、ベクトルロード格納ユニットは、異なるベクトルアクセス命令からの個々のアクセスが限られた程度までインターリービングされ得るか、またはまったくインターリービングされ得ないかどうかを認識する。
【００６１】
このフラグは、設定された場合にはアクセスされるアドレスが特定の規則に従うためいくらかのインターリービングが起こり得ることを示すチェック済みアドレスモードフラグと呼称され得る。
【００６２】
インターリービングに関する制約は複数の方法で表され得るが、１つの方法は、第１要素アクセスが第１ベクトルの要素番号「ｊ」に関連付けられ、第２要素アクセスが第２ベクトルの要素番号「ｊ」に関連付けられたかどうかを考慮することである。インターリービングに関する最も簡単な制約の１つは、ｊがｋより小さい（ｊ＜ｋ）場合は第１要素アクセスが常に第２要素アクセスの前に行われなければならならず、ｊがｋより大きいかまたは等しい場合はその順序が逆転し得る（すなわち第２要素アクセスが第１要素アクセスの前に行われ得る）ことである。この文書において、われわれはこの制約を、インターリービングが「ｊ＜ｋ」制約を満足しなければならないと言うことにより、簡潔に説明する。
【００６３】
例外処理に対するサポートを簡略化するために、チェック済みアドレスモードフラグは、例外が取られた場合には、クリアされ得る。（このことは、チェック済みアドレスモードフラグが再びセットされるまで、最適化を無効化する。その結果、例外にわたってチェック済みアドレスモードフラグを保存することと、性能との間にトレードオフが存在する）。
【００６４】
フラグは、命令ストリーム内のスタート命令およびストップ命令により、セットされ得る。なお、これらの命令は、フラグをセットすることにより、インターリービングが現時点で起こり得ることを示す。それらは、別個の命令であってもよく、または他の命令と組み合わされてもよい。例えば、バックワード分岐がストップ命令として扱われ、それによりフラグがクリアされ得る。
【００６５】
さらに、１つのループ反復の始点は以前のループ反復の終点でもあるので、ループにおいてスタート命令およびストップ命令を単一の命令に組み合わせることは有用であり得る。このことは、異なるループ反復からの要素アクセスが、依存性チェックを実行する事なく安全に順序変更できないことを示す、ループ反復間のバリアのように挙動する。
【００６６】
スタート命令は正当な順序変更の異なるパターンを示し得る。例えば、上述の「ｊ＜ｋ」を要求する代わりに、それは、「ｊ＜ｋ」であるならば要素アクセスは順序変更され得ることを、さらに一般的には、何らかの定数「ｄ」に対して、要素アクセスは「ｊ＜ｋ＋ｄ」であるならば順序変更され得ることを、示し得る。（このパターンは、ループが「．．．＝Ａ［ｉ＋ｄ］；Ａ［ｉ］＝．．．」などのコードを含む場合に起こる）その場合は、この定数「ｄ」のための格納器が必要となり、これは図３における格納器８５として示される。
【００６７】
スタート命令およびストップ命令を用いる代わりに、「部分的バリア」が用いられ得る。従来のバリアは要素アクセスの順序変更を妨げる一方で、「部分的バリア」は「ｊ＜ｋ」の場合に要素の順序変更を妨げる。
【００６８】
スタート命令およびストップ命令を用いる代わりに、われわれは現行の「バリアモード」を設定する命令を有し得る。バリアモードは、「フル」、「部分的」、または「無」のうちの１つであり得る。現行バリアモードは、メモリアクセスの前に暗黙的なバリア、部分的バリア、または無バリアのいずれかを挿入することにより、全部の後続メモリアクセスに影響を及ぼす。現行バリアモードを「部分的」に設定することはスタート命令のように挙動し、現行バリアモードを「フル」に設定することはストップ命令のように挙動する。
【００６９】
図３は図２のベクトルロード格納ユニット１０をより詳細に示す。このベクトルロード格納ユニット内に、２つの保留中のベクトルデータアクセス命令から受け取られたインデックス値１２および１４を比較するための比較回路５７が存在する。なお、これらのインデックス値はそれぞれの命令内での特定のデータアクセス要求の要素位置を示す。比較の結果に基づいて次に発行するデータアクセス要求を選択する選択回路５８も存在する。
【００７０】
ベクトルロード格納ユニット１０はフラグ値格納器８０も備える。このフラグ値格納器８０は、プロセッサにより設定されたフラグ値を格納し、設定されると、２つのベクトルデータアクセス命令により指定された個々のデータアクセスが特定の程度までインターリービングされ得ることをＬＳＵ１０に対して示す。個々のデータアクセスがインターリービングされ得る程度は、所定値格納器８５に格納された値により決定され得る。この値はデコーダにより設定され、インターリービングの程度の表示を提供する。
【００７１】
この事例において、フラグ８０はインターリービングが許可されるよう設定され、格納器８５の所定値はゼロである。このことは、２つのベクトルデータアクセス命令からのデータアクセスがインターリービングされ得る程度が、２つのデータアクセス命令からのアクセスが第１データアクセス命令からの対応するアクセスを追い越してはならない程度であることを示す。換言するとインデックス１（その命令内における第１ベクトルデータアクセス命令からの現在保留中のデータアクセスの位置を示す）はインデックス２（その命令内における第２ベクトルデータアクセス命令からの現在保留中のデータアクセスの位置を示す）よりも大きくなければならない。この制約が満足されるならば、第２命令からのデータアクセスがメモリに対して発行され、この制約が満足されないならば第１命令からのデータアクセスはメモリに対して発行されない。
【００７２】
したがって、アクセスは進行し、それぞれの命令からのアクセスが実行されるとインデックスカウンタ１２および１４はインクリメントされる。したがって、最初インデックス１およびインデックス２が０であるならば、これら２つの値が等しくしたがってインデックス１がインデックス２よりも大きくなければならないという要件が満足されないことを比較回路５７が判定するであろう。したがって選択回路５８は命令１からのデータアクセスを選択し、命令１に対するアドレス０がデータアクセスとして発行され、インデックス１がインクリメントされる。次に、２つのインデックス値の比較は、インデックス１がインデックス２よりも大きいことを見出し、したがって、命令２からのアクセスインデックスが命令１からのアクセスインデックスよりも小さくなければならないという制約が満足され、理論上は選択され得るが、命令２からのアクセスが優先的に選択される。したがって命令２からのアドレス０が次のデータ要素にアクセスするために用いられる。このロード格納ユニットが単一のサイクル内で２つの命令をアクセスできるならばこれら２つの命令が最初のサイクル内で選択され一緒に実行されるであろう点に注意すべきである。ベクトルロード格納ユニットはこのようにして実行されるアクセスを選択し続ける。このようにして２つの命令が同時に処理され、命令２のレイテンシが低減される。
【００７３】
上述のように、値を格納するための所定値格納器８５が存在する。前述の実施形態では、選択判断基準は単に、第２命令からのアクセスが第１命令を追い越してはならないということであり、この値はしたがってゼロに設定される。しかし、いくつかの場合では異なる要件が存在し得る。異なる要件が存在する場合、所定値８５は異なる所定値を格納し、選択判断基準は、インデックス２とインデックス１との間の差異がこの格納された所定値よりも小さくなければならない、となり得る。この判断基準が満足されるならば、いずれのアクセスも選択され得るが、後の命令からのデータアクセスが優先的に選択される。
【００７４】
図５は、複数のメモリバンクに格納されたデータをアクセスするための本発明の１つの実施形態に係る多重ベクトルロード／格納ユニットを示す。この点について、ギャザースキャッタベクトルメモリアクセス命令を有するプログラムは高いアドレス帯域幅を有する（すなわちより多くのアドレスが単位サイクルあたりでメモリシステムに提供される）ことができ、したがって、サイクル毎に多重アクセスを実行できるメモリシステムからの利点を有することができる。これは、メモリシステムをいくつかの独立的にアクセス可能なバンクに分割し、ベクトルメモリアクセスが一般に複数のバンクをアクセスし、それによりアクセスが互いに対して並行的に実行されることが可能となるようアドレスマップを配列することにより、しばしば実装される。このバンク化は、メモリシステムのいくつかの異なる部分（すなわち、ＴＬＢ、Ｌ１キャッシュ、Ｌ２キャッシュ、ＤＲＡＭコントローラ、その他）に適用され得る。
【００７５】
図５において、ベクトルロード格納ユニット１０は、２つの構成要素１５と構成要素１７と（第１ベクトルデータアクセス命令に応答してデータにアクセスする第１構成要素１５と、第２ベクトルデータアクセス命令に応答してデータにアクセスする第２構成要素１７と）を備える。
【００７６】
これらの構成要素１５および１７の両方がレジスタ格納器２５および２７を有する。レジスタ格納器２５は保留中のベクトルデータアクセス命令のアドレス要素を格納するためのものであり、レジスタ格納器２７はこれらのアクセス命令に対応するデータを格納するためのものである。したがって、保留中の命令が書き込み命令である場合、書き込み命令により格納されるデータはレジスタ内に保持されるであろう。一方、保留中の命令が読み出し命令である場合、読み出されるデータを格納する空間がレジスタ内に存在する。
【００７７】
バンク比較器３５および３７も各構成要素内に存在する。これらのバンク比較器３５および３７は、アクセスされるデータ要素のアドレスを分析し、そのアドレスから、メモリバンク１００、１０２、１０４、および１０７のうちのどのメモリバンクがアクセスされるかを判定する。
【００７８】
したがって第１ベクトルデータ命令はベクトルロード格納ユニット構成要素１５において受け取られ、レジスタ２５に格納される。第２ベクトルデータアクセス命令はベクトルロード格納ユニット構成要素１７において受け取られ、レジスタ２７に格納される。これの事例において、それらの両方が書き込み命令である。
【００７９】
インデックスカウンタ４５および４７は、それぞれ最初は０に設定され、これらのベクトルアクセス要求に対応するレジスタ２５および２７における第１アドレス要素がアクセスされ、アドレスがどのバンク内にあるかが判定される。比較ユニット５７は２つのインデックスを比較し、その結果をバンクアクセス制御ユニット９０に送る。インデックス４７により指定されたアドレス要素にアクセスすることに加えて、ベクトルロード格納ユニット１５内の次のアドレス要素もアクセスされ、それがどのバンクにあるかが判定される。これらの情報の全部がバンクアクセス制御ユニット９０に提供され、バンクアクセス制御ユニット９０は、どのアクセスがメモリシステムに伝達されるべきかを判定する。
【００８０】
図４は図５のバンクアクセス制御ユニット９０をより詳細に示す。上述のように、信号は２つのロード格納ユニット構成要素１５および１７からこのユニットにおいて受け取られる。この事例において、バンクアクセス制御ユニット９０により考慮される３つの保留中のアクセス要求が存在する。これらの信号のそれぞれは、アドレスと、各信号に関連付けられたデータと、それが読み出しであるか書き込みであるかの表示と、を含む。３つの信号は、第１ベクトルロード格納ユニット１５から受け取られた第１ベクトルデータアクセス命令からの、要素に対する２つのデータアクセス要求ａｊおよびａｊ＋１と、第２ベクトルロード格納ユニット構成要素１７から受け取られた第２ベクトルデータアクセス命令からのデータアクセス要求ｂｋと、を含む。
【００８１】
これらのアドレスが見出されるバンクを示す追加情報もまた送られる。各バンクに対して、この追加情報は比較回路１０９によりバンクＩＤと比較され、どのアクセスがどのバンクに対して保留中であるかが判定される。特定のバンクに対して１つのみのアクセスが保留中である場合、そのアクセスはそのバンクに伝達され、進行することが許可される。
【００８２】
一方、２つ以上のアクセスが１つのバンクに対して保留中である場合、アクセス優先順位付け回路９５は、どのアクセスが最初に実行されるかを判定する。アクセス優先順位付け回路９５はロード／格納ユニット１０内の比較回路５７からの信号に応答してこれを判定する。この比較回路はｋがｊより小さいかどうかを判定する。ｋがｊより小さいと、ｂｋは選択されることができ、選択される。ｋがｊより小さくないと、第２データアクセス命令からのアクセスが事実上、第１ベクトルデータアクセス命令からのアクセスに追いつき、第２データアクセス命令からのアクセスは、第１ベクトルデータアクセス命令が再び優位を獲得する間、しばらくの間抑制される必要がある。この場合アクセスａｊが優先される。ａｊがｂｋと同一のバンクに対するものではなくしかしａｊ＋１が当該のバンクに対するものである場合、優先順位付け回路９５は、ｋがｊ＋１よりも小さいかどうかに基づいてどのアクセスを選択するかを判定するであろう。ｋがｊ＋１よりも小さい場合、ｋｂが選択され得る。一方、ｊ＋１がｋよりも小さい場合、アクセスａｊ＋１が優先権を有するであろう。
【００８３】
このように、特定のサイクルの間、バンクは互いに対して独立的にアクセスされることができ、一般的に強制される制約は、異なるバンクに対するアクセスの間で強制されないが、同一のバンクに対するアクセスには強制される。これは明らかに、より多くのアクセスが実行されることを可能にするが、追加的な比較および制御の回路のオーバーヘッドを有する。
【００８４】
要約すると、バンク内のアクセスを安全にインターリービングするメモリシステムの簡単な具体化は
１ブロックのコードの始点および終点を示す、１対の新規命令と、
「チェック済みアドレスモード」で実行中であるかどうかを示すフラグを有し、
スタート命令に遭遇するとフラグを設定し、終了命令に遭遇するとフラグをクリアし、
それぞれが、
どの要素が次にアクセスされるかを示す要素インデックスｊまたはｋと、
ＶＭＵが、読み出し、書き込み、またはアイドルを実行中であるかどうかを示すフラグと、
アドレスと、アクセスが書き込みである場合には各保留中の要素アクセスの値と、からなる２つまでの保留中の要素アクセスのバッファと、
保留中の要素アクセスの個数のカウントと、
各保留中の要素アクセスに対するバンク識別ロジックと、
を備える、２つのベクトルメモリユニット（ＶＭＵ）を有し、
２つのＶＭＵにおける要素インデックスを比較する比較器を有し、
それぞれが、
ＶＭＵのいずれかからの保留中の要素アクセスのいずれかを選択するマルチプレクサと、
ｊ＜ｋの場合には：
ａｊがこのバンクに対するものであるならば、ａｊを選択し、
それ以外の場合には、このバンクに対するアクセスは実行せず、
ｊ＞＝ｋの場合には：
ａｊおよびｂｋの両方がこのバンクに対するものであるならば、ｂｋを選択し、
ａｊがこのバンクに対するものでありｂｋが異なるバンクに対するものであるならば、ａｊを選択し、
ｂｋがこのバンクに対するものでありａｊが異なるバンクに対するものであるならば、ｂｊを選択し、
ａｊおよびｂｋが異なるバンクに対するものであるならば：
ａ（ｊ＋１）がこのバンクに対するものであるときにはａ（ｊ＋１）を選択し、
それ以外の場合には、このバンクに対するアクセスは実行しないよう、
保留中の要素アクセス［ａｊ，ａ（ｊ＋１）］および［ｂｋ，ｂ（ｋ＋１）］を選択する制御ロジックと、
を備える、４つのバンクを有し、
各ＶＭＵから選択されたアクセスの個数にしたがってｊおよびｋの値を更新するロジックを有する、
ロード格納ユニットと、
からなる。
【００８５】
この具体化は、同一のバンクに対するアクセスが単一アクセスに合体され得るよう、後に説明する合体実装と組み合わせることを含む様々な方法で改善されることができる。
【００８６】
図６Ａはベクトル化されたコードをコンパイルするための方法におけるステップを例示説明するフローチャートを示す。この実施形態では、コンパイラは、スカラー命令を含むコンピュータプログラムにおけるループを認識し、これらをベクトル命令に変換する。コンパイラは、ループをベクトル化するタスクが分析を実行し、それによりどのメモリ依存が存在するかを判定することを含むことを認識する。したがって、コンパイラが正常にループをベクトル化すると、コンパイラは、ベクトル化されたループ内のメモリアクセスが競合しないことをすでに知る。したがって、データアクセスのインターリービングが起こり得ることをコンパイラは認識し、コードを処理する処理システムにこれを示すために、コンパイラはループ本体の始点においてスタート命令を生成し、ループ本体の終点において終了命令を生成する。
【００８７】
この基本的方式は様々な方法で向上されることができる。
【００８８】
いくつかの状況において、コンパイラは、異なるパターンの正当な順序変更を示す変更されたスタート命令を挿入し得る。例えば、１ブロックのコードの内部で実行される全部のアクセスが別個のアドレスに対するものであることをコンパイラが判定した場合、コンパイラは、「ｊ＜＝ｋ」の制約を満足する順序変更が正確であることを、または任意の順序変更が正確であることを示すスタート命令を発することができる。
【００８９】
米国特許公開第２００８／０２８８７５４号では「ＣｈｅｃｋＨａｚａｒｄ」命令が開示されている。「ＣｈｅｃｋＨａｚａｒｄ」命令は２つのベクトルをテストし、それにより、一方のベクトルの位置ｊにおけるアドレスが他方のベクトルのいくつかの位置ｋ（ｊ＜ｋ）の任意のアドレスと重複するかどうかを判定する。この命令は、ループがベクトル化されることを妨げるであろう任意の重複を動的にテスト（および対処）するために用いられることができる。この命令は、インターリービングが可能であるかどうかをチェックするためのテストを実際に実行するため、本発明の実施形態に関して特に良好に作用する。ｊ＜＝ｋなどの位置をチェックするＣｈｅｃｋｈａｚａｒｄＸ命令も存在する。したがって、この命令はコードをテストするために用いられてきたが、アクセスがインターリービングされることができることの表示は、フラグを設定することにより、または限定的インターリービングスタート命令の使用により、データ処理システムに提供されることができる。
【００９０】
コンパイラは、いくつかの場合ではソフトウェアで形成され得るが、ハードウェアで構成されてもよい。図６Ｂはハードウェアコンパイラを概略的に示す。ハードウェアコンパイラ内では、命令ストリームが分析回路に入力され、分析回路内では命令ストリームが分析され、ループが特定され、ベクトルコードが形成される。係るベクトルのインターリービングも特定されるコードの位置と、スタート命令およびストップ命令とが、コードに挿入され、次にこのコードは、処理回路により実行されることができるコードへと変換回路により変換される。
【００９１】
図７は、同一のキャッシュにアクセスする２つのベクトルロード格納ユニットが、それらのアクセスが合体されることを可能にする追加的な制御回路を有することができる方法の１例を示す。この点に関して、図７は、各ロード格納ユニットからのアクセスのインデックスを比較し、それによりいずれのインターリービング規則も破られてないことをチェックするよう作用する関連する制御回路と、保留中のデータアクセスのアドレスをチェックする合体回５９路と、を有する２つのベクトルロード格納ユニット１５および１７を概略的に示す。なお、保留中のデータアクセスのアドレスが同一ラインに対するものであり、それらを合体することがインターリービング規則を破らない場合は、それらは単一のアクセスに合体される。
【００９２】
アクセスを同一のキャッシュラインに合体することは、性能の改善およびエネルギー削減の両方のために有利である。ベクトルアクセスにおいて、合体は通常は局所性を利用するために単一のベクトルアクセス内で行われるが、２つのベクトルアクセスにおける対応する要素位置の間に顕著な局所性が存在することは一般的である。例えば、これら２つの命令文、すなわち
Ａ［ｉ］［ｊ］．ｘ＝ｐ；
Ａ［ｉ］［ｊ］．ｙ＝ｑ；
を含むループのベクトル化は、２つのベクトル格納命令を含むループを生成するであろう。当該のループの所与の反復において、第１ベクトル格納命令はアドレス：［１０００，２０００，３０００，４０００，．．．］に書き込み、その一方で、第２ベクトル格納命令はアドレス［１００４，  ２００４，  ３００４，  ４００４，．．．］に書き込む。この場合、各ベクトルアクセス内に局所性は存在しないが、かなりの局所性がベクトルアドレスの間に存在し、理想的には、アクセスは［１０００，１００４，２０００，２００４，３０００，３００４，４０００，４００４，．．．］の順序で行われるであろう。
【００９３】
これは、図８Ａに示すようにアクセスが単一のアクセスに合体されることを可能にする。図８Ａは、単一のアクセスに合体されたアクセスａ０およびｂ０を有する合体されたアクセスパターンを示す。
【００９４】
実際、空間局所性がベクトルアクセス内に、ならびにベクトルアクセス間に、見出され得る。例えば、第１ベクトルアクセスはアドレス［１０００，１００８，１０１６，１０２４，．．．］における要素にアクセスし得る一方で、第２ベクトルアクセスはアドレス［１００４，１０１２，１０２０，１０２８，．．．］における要素にアクセスし得る。この場合、ベクトルアクセス内の要素アクセスを合体し、ベクトルアクセス間のアクセスを合体することが望ましい。係る場合が図８Ｂに示され、図８Ｂでは、第１ベクトル演算からの要素アクセスの対が第２ベクトル演算からの要素アクセスの対とともに合体される。これは、合体のない場合の１６サイクルまたは合体がベクトル間またはベクトル内でのみ起こる場合の８サイクルと比較して、４サイクルで実行する。
【００９５】
コードがベクトル化されインターリービングが性能を改善する方法のいくつかの簡単な例が、以下で提供される。
【００９６】
順次てきなコード（ベクトル化以前）
ｆｏｒ（ｉ＝０；  ｉ＜Ｎ；  ＋＋ｉ）  ｛
ａ［ｉ］＋＋；
ｂ［ｉ］  ＝  ａ［ｉ］；
｝
【００９７】
限定的なインターリービングを有することができるベクトル化されたコード
ｆｏｒ（ｉ＝０；  ｉ＜Ｎ；  ｉ＋＝８）  ｛
ｓｔａｒｔ；
ｖ１＝ｖｌｏａｄ（＆ａ［ｉ］）；
ｖ２＝ｖａｄｄ（ｖ１，１）；
ｖｓｔｏｒｅ（＆ａ［ｉ］，ｖ２）；／／このベクトル格納と、このベクトルロードが、
ｖ３＝ｖｌｏａｄ（＆ａ［ｉ］）；  ／／対象となるものである
ｖｓｔｏｒｅ（＆ｂ［ｉ］，ｖ３）；
ｓｔｏｐ；
｝
【００９８】
これは、第１のｖｓｔｏｒｅと第２のｖｌｏａｄとの間で競合が起こり得るために、限定的なインターリービングを可能にする。
【００９９】
限定的なインターリービングを用いないと（すなわちベクトルロード／格納が制約なしに順序の変更が可能である）、高速であるが不正確となるであろう。書き込み（ｖｓｔｏｒｅからの）および読み出し（ｖｌｏａｄからの）の１つの可能な順序変更は、ａ［０］への書き込みの前にａ［０］からの読み出しを不正確に実行するであろう。
【０１００】
インターリービングをまったく用いないと、［０］．．ａ［７］のへの書き込みの全部が［０］．．ａ［７］からの読み出しをスタートする前に実行されなければならないため、正確であるが、不必要に低速となるであろう。
【０１０１】
限定的なインターリービングを用いると（すなわちｊ＜ｋの場合にのみ要素ｋへのロードが要素ｊからの格納の前に起こることができる）、ベクトル化されたコードはより高速に実行され、正確である。
【０１０２】
わずかな変更をコードに加えることにより、要求される比較の正確な詳細はわずかに変化する（例はわずかにより現実的になる）。
ｆｏｒ（ｉ＝０；  ｉ＜Ｎ；  ＋＋ｉ）  ｛
ａ［ｉ］＋＋；
ｂ［ｉ］＝ａ［ｉ＋２］；  ／／  ａ［ｉ］をａ［ｉ＋２］に変更
｝
【０１０３】
この変化に関して、強制される条件は「ｊ＜ｋ＋２」である。
または、より一般的に：
ｆｏｒ（ｉ＝０；ｉ＜Ｎ；＋＋ｉ）  ｛
ａ［ｉ］＋＋；
ｂ［ｉ］＝ａ［ｉ＋ｄ］；  ／／  ａ［ｉ］をａ［ｉ＋ｄ］に変更した
｝
【０１０４】
この変化に関して、強制される条件は「ｊ＜ｋ＋ｄ」である。
【０１０５】
このことを生じさせるために、ＶＭＵ内の比較ハードウェアが「ｊ＜ｋ＋ｄ」をテストすることを知るよう、われわれはｄの値を「限定的インターリービングスタート」命令にエンコードできる。
【０１０６】
最後に、本発明の実施形態の顕著な特長は、アドレス比較器がインターリービングをサポートするために必要ではなく、限定的インターリービングにより直接的にサポートされる順序変更を越えて追加的順序変更が可能となるよう、アドレス比較器を追加することが可能である点に注意すべきである。それは、ループの１つの反復と、次の反復、ループの前／後のコード、または次のベクトル化されたループとの間で、アクセスの少量のインターリービングを可能にする為である。比較器はなすべき作業が少ないため、より少数の比較器を用いて、および／またはより頻繁に比較器をクロックゲートすることにより、良好な性能が達成されることができる。
【０１０７】
本発明の実施形態の様々な特徴の要約が以下で図９Ａ〜図１５を参照して説明される。
【０１０８】
図９Ａは第１の安全にインターリービングされたアクセスパターンを示す。なおこの図面では、時間は左から右に進行し、第１ベクトルアクセスからの要素アクセスａ０〜ａ７は、第２ベクトルアクセスからの要素アクセスｂ０〜ｂ７から別個のライン上にある。ｊ＜ｋである場合、アクセスａｊはアクセスｂｋの前に起こることに注意すべきである。
【０１０９】
図９Ｂは他の安全にインターリービングされたアクセスパターンを示す。なおこの図面では、時間は左から右に進行し、第１ベクトルアクセスからの要素アクセスａ０〜ａ７は、第２ベクトルアクセスからの要素アクセスｂ０〜ｂ７から別個のライン上にある。ｊ＜ｋである場合、アクセスａｊはアクセスｂｋの前に起こることに注意すべきである。
【０１１０】
図９Ｃは非安全なアクセスパターンを示す。なおこの図面では、時間は左から右に進行し、第１ベクトルアクセスからの要素アクセスａ０〜ａ７は、第２ベクトルアクセスからの要素アクセスｂ０〜ｂ７から別個のライン上にある。アクセスｂ１はアクセスａ１の前に起こる。これは、ａ１およびｂ１が同一アドレスにアクセスする場合、不正確な結果を与え得る。（ｂ２およびａ２も不正確に順序変更される。）
【０１１１】
アクセスを同一キャッシュラインに合体すること、およびアクセスをバンクされたメモリに合体することに関する２つの実施形態が以下で説明される。
【０１１２】
上述のように、例外処理に対するサポートを簡略化するために、チェック済みアドレスモードフラグは、例外が取られた場合には、クリアされ得る。（このことは、他のスタート命令が遭遇されるまで、最適化を無効化する。その結果、例外にわたってチェック済みアドレスモードフラグを保存することと、性能との間にトレードオフが存在する。）
−  スタート命令およびストップ命令は他の命令と組み合わされてもよい。例えば、バックワード分岐がストップ命令として扱われることができる。
-  １つのループ反復の始点は以前のループ反復の終点でもあるので、ループにおいてスタート命令およびストップ命令を単一の命令に組み合わせることは有用である。このことは、異なるループ反復からの要素アクセスが、依存性チェックを実行する事なく安全に順序変更できないことを示す、ループ反復間のバリアのように挙動する。
−  スタート命令は正当な順序変更の異なるパターンを示し得る。例えば、上述の「ｊ＜ｋ」を要求する代わりに、それは、「ｊ＜ｋ」であるならば要素アクセスは順序変更され得ることを、さらに一般的には、何らかの定数「ｄ」に対して、要素アクセスは「ｊ＜ｋ＋ｄ」であるならば順序変更され得ることを、示し得る。（このパターンはループが「．．．＝Ａ［ｉ＋ｄ］；Ａ［ｉ］＝．．．」などのコードを含む場合に起こる。）
-  スタート命令およびストップ命令を用いる代わりに、われわれは「部分的バリア」を用いることができる。従来のバリアは要素アクセスの順序変更を妨げる一方で、「部分的バリア」は「ｊ＜ｋ」の場合に要素の順序変更を妨げる。
−  スタート命令およびストップ命令を用いる代わりに、われわれは現行の「バリアモード」を設定する命令を有し得る。バリアモードは、「フル」、「部分的」、または「無」のうちの１つであり得る。現行バリアモードは、メモリアクセスの前に暗黙的なバリア、部分的バリア、または無バリアのいずれかを挿入することにより、全部の後続メモリアクセスに影響を及ぼす。現行バリアモードを「部分的」に設定することはスタート命令のように挙動し、現行バリアモードを「無」に設定することはストップ命令のように挙動する。
【０１１３】
２つのアドレスのベクトルをテストし、それにより、一方のベクトルの位置ｊにおけるアドレスが他方のベクトルのいくつかの位置ｋ（ｊ＜ｋ）の任意のアドレスと重複するかどうかを判定する、「ＣｈｅｃｋＨａｚａｒｄ」命令。この命令は、ループがベクトル化されることを妨げるであろう任意の重複を動的にテスト（および対処）するために用いられることができる。この命令は、正にわれわれが注目する場合についてテストするため、本発明の実施形態に関して特に良好に作用する。（ｊ＜＝ｋなどの位置をチェックするＣｈｅｃｋｈａｚａｒｄＸ命令も存在する。）
【０１１４】
スタート命令／終了命令をベクトル化されたコードに発する能力を有するコンパイラも説明される。これは、
−  ループをベクトル化するコンパイラ、
を要求し、
−  このコンパイラは、スタート命令をループ本体の始点において挿入し、終了命令をループ本体の終点において挿入する。（ループをベクトル化するタスクは、分析を実行し、それにより、どのメモリ依存が存在するかを判定することを伴う。したがって、コンパイラが正常にループをベクトル化すると、コンパイラは、ベクトル化されたループ内のメモリアクセスが競合しないことをすでに知る。
この基本的方式は様々な方法で向上されることができる。
−  いくつかの状況において、コンパイラは、代替的に、スタート命令をループの前に、終了命令をループの後に挿入できる。例えば、コンパイラは、ループにより実行される全部のアクセスが別個のアドレスに対するものであることをコンパイラが判定した場合、このことを行う。
−  いくつかの状況において、コンパイラは、異なるパターンの正当な順序変更を示す変更されたスタート命令を挿入し得る。例えば、１ブロックのコードの内部で実行される全部のアクセスが別個のアドレスに対するものであることをコンパイラが判定した場合、コンパイラは、「ｊ＜＝ｋ」が正確であることを、または任意の順序変更が正確であることを示すスタート命令を発することができる。
【０１１５】
キャッシュアクセスの合体
アクセスを同一のキャッシュラインに合体することは、性能の改善およびエネルギー削減の両方のために有用である。ベクトルアクセスにおいて、合体は通常はベクトル内の局所性を利用するために単一のベクトルアクセス内で行われるが、２つのベクトルアクセスにおける対応する要素位置の間に顕著な局所性が存在することは一般的である。例えば、これら２つの命令文、すなわち
Ａ［ｉ］［ｊ］．ｘ＝ｐ；
Ａ［ｉ］［ｊ］．ｙ＝ｑ；
を含むループのベクトル化は、２つのベクトル格納命令を含むループを生成するであろう。当該のループの所与の反復において、第１ベクトル格納命令はアドレス：［１０００，２０００，３０００，４０００，．．．］に書き込み、その一方で、第２ベクトル格納命令はアドレス［１００４，２００４，３００４，４００４，．．．］に書き込む。この場合、各ベクトルアクセス内に局所性は存在しないが、かなりの局所性がベクトルアドレスの間に存在し、理想的には、アクセスは［１０００，１００４，２０００，２００４，３０００，３００４，４０００，４００４，．．．］の順序で行われるであろう。
【０１１６】
これは、以下の図１０に示すようにアクセスが単一のアクセスに合体されることを可能にする。
【０１１７】
以下は、係る合体の実行を可能にする本発明の実施形態の具体化を説明する。
−  １ブロックのコードの始点および終点を示す、１対の新規命令
・  「チェック済みアドレスモード」で実行中であるかどうかを示すフラグを有し、
・  スタート命令に遭遇するとフラグを設定し、終了命令に遭遇するとフラグをクリアし、
・  それぞれが、
どの要素が次に格納されるか示す要素インデックスｊまたはｋと、
ＶＭＵが、読み出し、書き込み、またはアイドルを実行中であるかどうかを示すフラグと、
（ＶＭＵがアイドル状態でない場合に）ＶＭＵにおいて保留中のアクセスが存在するかどうかを示すフラグと、
（保留中のアクセスが存在する場合に）次の保留中のアクセスのアドレスと、
（次の保留中のアクセスが書き込みである場合に）次の保留中のアクセスの値と、
を備える、２つのベクトルメモリユニット（ＶＭＵ）を有し、
・  ２つのＶＭＵにおける要素インデックスを比較する比較器を有し、
・  ＶＭＵの次の保留中のアクセスのアドレスが同一のキャッシュラインに対するものであるかどうかを比較するための比較器を有し、
・    チェック済みアドレスモードフラグがクリアであるとき、第１ＶＭＵがアイドルであるか、または両方のアクセスが読み出しである場合、アクセスは第１ＶＭＵから取られ、
チェック済みアドレスモードフラグが設定されているとき、ｊ＜＝ｋであり且つ次の保留中のアクセスが同一のキャッシュラインに対するものである場合、第１ＶＭＵおよび第２ＶＭＵは単一のキャッシュアクセスに組み合わされ、
チェック済みアドレスモードフラグが設定され、次の保留中のアクセスが異なるキャッシュラインに対するものであり、ｊ＜ｋであるとき、第２ＶＭＵからのアクセスが選択され、
それ以外の場合は、第２ＶＭＵからのアクセスが選択されるよう、
一方のＶＭＵからまたは他方のＶＭＵからの次の要素を選択するためのマルチプレクサを有する、
−  ロード格納ユニット
【０１１８】
これは、合体され得る要素アクセスを検出するために単一のアドレス比較器を使用すること、および２つのベクトル演算のそれぞれから１つの要素アクセスを同時格納することのみを要求すること、が理解されるであろう。本発明の実施形態を利用することがなければ、同一程度の順序変更は、第１ベクトル演算からの全部の要素アクセスを同時格納することを必要とし、７つのアドレス比較器を必要とする（８のベクトル長さに対して）であろう。
【０１１９】
実際、空間局所性がベクトルアクセス内に、ならびにベクトルアクセス間に、見出されることができる。例えば、第１ベクトルアクセスはアドレス［１０００，１００８，１０１６，１０２４，．．．］における要素にアクセスし得る一方で、第２ベクトルアクセスはアドレス［１００４，１０１２，１０２０，１０２８，．．．］における要素にアクセスし得る。この場合、ベクトルアクセス内の要素アクセスを合体し、ベクトルアクセス間でアクセスを合体することが望ましい。図１１は係る場合を示す。なお係る場合においては、第１ベクトル演算からの要素アクセスの対が第２ベクトル演算からの要素アクセスの対とともに合体される。これは、合体のない場合の１６サイクルと比較して、または合体がベクトル演算間でのみもしくはベクトル演算内でのみ起こる場合の８サイクルと比較して、４サイクルで実行する。
【０１２０】
図１１は、合体されたアクセスパターンを示す。なおこの図面では、時間は左から右に進行し、第１ベクトルアクセスからの要素アクセスａ０〜ａ７は、第２ベクトルアクセスからの要素アクセスｂ０〜ｂ７から別個のライン上にある。第１ベクトル演算からの連続した要素アクセスが、相互と、および第２ベクトル演算からの連続した要素アクセスと、合体され、同時に起こることに注意すべきである。
【０１２１】
上記の具体化は、
−    複数のアクセスのアドレス（および、書き込みに対してはデータ）をバッファリングするよう、および
各ＶＭＵ内で近接する要素アクセスのアドレスを比較し、それにより、合体の候補となる各ＶＭＵ内の連続的な要素アクセスのシーケンスが特定されるよう、
両方のＶＭＵを拡張することにより、この挙動をサポートするよう強化されることができる。これは、要素アクセスが連続的にＶＭＵに加えられる場合、ＶＭＵ毎に１つの追加的な比較を必要とする。
−  次の要素アクセスのアドレスが同一のキャッシュラインに対するものであり、第１ＶＭＵがそのキャッシュラインに対するｍ個の連続したアクセスを有し、第２ＶＭＵがそのキャッシュラインに対するｎ個の連続したアクセスを有する場合、第１ＶＭＵからのｍ個の要素と第２ＶＭＵからの「ｍｉｎ（ｊ＋ｍ，ｋ＋ｎ）−ｋ」個の要素が単一のキャッシュアクセスに合体されることができる。
【０１２２】
バンクされたメモリアクセス
ギャザースキャッタベクトルメモリアクセス命令を有するプログラムは高いアドレス帯域幅を有する（すなわちより多くのアドレスが単位サイクルあたりでメモリシステムに提供される）ことができ、したがって、サイクル毎に多重アクセスを実行できるメモリシステムからの利点を有することができる。これは、メモリシステムをいくつかの独立的にアクセス可能なバンクに分割し、ベクトルメモリアクセスが一般に複数のバンクをアクセスし、それによりアクセスが互いに対して並行的に実行されることが可能となるようアドレスマップを配列することにより、しばしば実装される。このバンク化は、メモリシステムのいくつかの異なる部分（すなわち、ＴＬＢ、Ｌ１キャッシュ、Ｌ２キャッシュ、ＤＲＡＭコントローラ、その他）に適用され得る。例えば、キャッシュは４つの独立的にアクセス可能なバンクＢ０、Ｂ１、Ｂ２、およびＢ３と、４つのバンクのうちのどのバンクがそのアドレスを格納するために用いられる要素のアドレスのビット６および７と、に分割され得る。要素アクセスａ０〜ａ７からなるベクトルアクセスは、各要素アクセスのアドレスのビット６および７を調査し、各要素アクセスを４つのバンクのうちの１つに誘導することにより、実行されることができる。図１２はアクセスパターンを示す。なお、サイクル毎に最大で２要素アクセスの要素アクセスを順番に発行するベクトルメモリユニットを仮定して、このアクセスパターンは、アドレス［６０，７６，９２，１０８，１２４，１４０，１５６，１７２］（バンク［Ｂ０，Ｂ１，Ｂ１，Ｂ１，Ｂ１，Ｂ２，Ｂ２，Ｂ２，Ｂ２，Ｂ３］にマッピングする）に対するベクトルアクセスの結果として生成されるものである。完全なベクトル演算は、たとえどのバンクも４つ以上の要素アクセスを実行しないとしても、６サイクルを必要とする。
【０１２３】
図１３はアクセスパターンを示す。なおこのアクセスパターンは、チェック済みアドレスモードでないとき、第１ベクトル演算が、アドレス［１９２，１３２，１９６，１３６，２００，１４０，２０４，１４４］（バンク［Ｂ３，Ｂ２，Ｂ３，Ｂ２，Ｂ３，Ｂ２，Ｂ３，Ｂ２］にマッピングする）に対する第２ベクトル演算に続くときに生成されるものである。アクセスパターンがチェック済みアドレスモードでない（すなわち本発明の実施形態が用いられていない）ため、第２ベクトル演算からのどの要素アクセスも、第１ベクトル演算からの全部の要素アクセスが終了するまで、実行されない。２つのベクトル演算は、完了するために１０サイクルを必要とする。
【０１２４】
図１４は、第２ベクトル演算が第１ベクトル演算と並行して進行することを許可することが安全ではないことを示す。この図面では、アクセスａ５およびアクセスｂ５が両方ともアドレス１４０に対するものであり、不正確にアクセスｂ５がアクセスａ５の前に実行されていることに注意すべきである。（このシーケンスが正当であった場合、７サイクルを必要としたことであろう。）
【０１２５】
図１５は、正確に実行する同一のアクセスパターンを示す。アクセスｂ５が第３サイクルで利用可能であったとしても、そのアクセスは、アクセスが各バンク内で安全にインターリービングされることを確保するために、アクセスａ５が実行されるまで拒否される。アクセスｂ４がａ４の前に実行されないことにも注意すべきである。なぜなら、ｂ４およびａ４は、両方がアクセス可能となるまで、同一のバンクにアクセスするかどうかの判定が不可能であるためである。同様に、アクセスｂ６はアクセスa６の前に実行されない。本発明の実施形態を利用することにより、このアクセスパターンは８サイクルで完了する。すなわち２サイクルが節約されたことになる。
【０１２６】
最後に、アドレス比較器がインターリービングをサポートするために必要ではないが、本発明の実施形態により直接的にサポートされる順序変更を越えて追加的な順序変更が可能となるよう、アドレス比較器を追加することが可能ことを述べることは価値がある。それは、ループの１つの反復と、次の反復、ループの前／後のコード、または次のベクトル化されたループとの間で、アクセスの少量のインターリービングを可能にする。比較器はなすべき作業が少ないため、われわれは、より少数の比較器を用いて良好な性能を達成でき、および／またはより頻繁に比較器をクロックゲートすることができる。
【０１２７】
図１６は、用いられ得る仮想機械の実装を示す。これまでに説明してきた実施形態は、関連する技術をサポートする特定の処理ハードウェアを操作するための装置および方法の形で、本発明を具体化するが、ハードウェア装置のいわゆる仮想機械の実装を提供することも可能である。これらの仮想機械の実装は、仮想機械プログラム５１０をサポートするホストオペレーティングシステム５２０を通常は実行するホストプロセッサ５３０上で実行される。通常、より大きい強力なプロセッサが、妥当なスピードで実行される仮想機械の実装を提供するために必要となる。しかし、係るアプローチは、互換性のために、または再利用の理由のために他のプロセッサに対してネイティブであるコードを実行することが望まれる場合等の特定の状況において正当化される。仮想機械プログラム５１０は、アプリケーションプログラム（またはオペレーティングシステム）５００を実行することにより、実際のハードウェア装置によりプログラムを実行することにより提供されるのと同一の結果を提供する能力を有する。したがって、実行されるデータアクセスの順序変更は、仮想機械プログラム５１０を用いて、アプリケーションプログラム５００内から実行され得る。
【０１２８】
本発明の例示的な実施形態が添付の図面を参照して本明細書において詳細に説明されてきたが、本発明がこれらの実施形態に精密に限定されるものではなく、様々な変化例および変更例が、添付の請求項により定義される本発明の精神および範囲から逸脱することなく、当業者により実施可能であることが理解されるであろう。
【図１】
2014532221.tif 000003
【図２】
2014532221.tif 000004
【図３】
2014532221.tif 000005
【図４】
2014532221.tif 000006
【図５】
2014532221.tif 000007
【図６Ａ】
2014532221.tif 000008
【図６Ｂ】
2014532221.tif 000009
【図７】
2014532221.tif 000010
【図８Ａ】
2014532221.tif 000011
【図８Ｂ】
2014532221.tif 000012
【図９Ａ】
2014532221.tif 000013
【図９Ｂ】
2014532221.tif 000014
【図９Ｃ】
2014532221.tif 000015
【図１０】
2014532221.tif 000016
【図１１】
2014532221.tif 000017
【図１２】
2014532221.tif 000018
【図１３】
2014532221.tif 000019
【図１４】
2014532221.tif 000020
【図１５】
2014532221.tif 000021
【図１６】
2014532221.tif 000022
【国際調査報告】
2014532221.tif 000023
2014532221.tif 000024
2014532221.tif 000025