効率的な同期および並列リダクション演算を可能にするベクトル命令

专利摘要:
ある実施形態では、プロセッサは、単一の命令に応答して複数のデータ要素に対して動作を実行するベクトル・ユニットと；前記ベクトル・ユニットに前記データ要素を与えるよう前記ベクトル・ユニットに結合された制御ユニットとを含みうる。前記制御ユニットは、第一のマスクのもとで実行される第一のベクトル命令および第二のマスクのもとで実行される第二のベクトル命令に応答して前記データ要素の少なくともいくつかに対して原子的なSIMD動作が実行されることを可能にする。他の実施形態も記載され、特許請求される。
公开号:JP2011514598A
申请号:JP2010548946
申请日:2009-03-27
公开日:2011-05-06
发明作者:キム，チャンギュ；キム，デヒョン；グエン，アンソニー，ディー．；クマール，サンジーヴ；スメリャンスキー，ミハイル；チェン，イエン−クワン；チュガニ，ジャティン；ヒューズ，クリストファー；リー，ヴィクター，ダブリュー．
申请人:インテル コーポレイション；
IPC主号:G06F9-34

专利说明:

[0001] 本発明はベクトル命令に関する。]
背景技術

[0002] 多くのアプリケーションは大量のデータ・レベルの並列を有し、単一命令複数データ（SIMD: single-instruction multiple-data）サポートから裨益できるべきである。SIMD実行では、単一の命令が複数のデータ要素に対して同時に作用する。これは典型的には、レジスタおよび演算論理装置（ALU）のようなさまざまな資源の幅を拡張して、それぞれ複数のデータ要素を保持するまたは複数のデータ要素に作用することを許容することによって実装される。]
発明が解決しようとする課題

[0003] しかしながら、そのような多くのアプリケーションは、かなりの時間を、疎な位置の集合に対する原子的な演算において費やし、そのためSIMDから受ける恩恵は限定的である。現在のアーキテクチャは原子的な（atomic）ベクトル演算をサポートしないからである。]
[0004] 多くのアプリケーションにおいて、しばしば同期プリミティブおよび並列リダクション演算がマルチプロセッサ・システムにおいて実行される。同期プリミティブ（synchronization primitives）は、複数のスレッドが協働的に作業するときにプログラムが正しい順序で実行されることを保証する。これらのプリミティブはしばしば、原子的な読み出し‐修正‐書き込み（read-modify-write）動作を使って実装される。リダクション（reduction）は、多くの科学アプリケーションにおいて見出される一般的な動作である。複数のスレッドが並列にリダクションを実行するとき、競争条件（race conditions）において正しさを保証するために、原子的な読み出し‐修正‐書き込みシーケンスが典型的には使用される。]
[0005] 現代の並列アーキテクチャは、データ・レベルの並列を用いて多くのアプリケーションのパフォーマンスを改善するためにSIMDユニットを備えている。SIMD効率を維持するために、そのようなアーキテクチャはSIMD算術演算だけでなく、SIMDメモリ読み出しおよび書き込みをも（収集‐分散（gather-scatter）ユニットを通じて）許容する。しかしながら、これらのアーキテクチャのいずれもSIMD原子的動作はサポートしない。その結果、こうした原子的動作はベクトル化できず、したがってスカラー・コードを使って実装しなければならない。これは、SIMD幅、すなわち同時に処理される要素数が大きい（たとえば16）場合は特に、SIMD効率を著しく劣化させることがある。]
[0006] 分散リダクション（scatter reductions）は多くのアプリケーションで一般的な動作である。たとえば、分散加算（scatter-add）演算は、第一の配列の複数の値を、インデックスの分布に従って第二の配列の選択された要素にリダクションする（すなわち加算する）ことを可能にするために使用できる。インデックスの分布はしばしばランダムでありうる。このため、複数の要素を並行して（すなわちSIMDモードで）効率的に処理することは難しい。]
[0007] ヒストグラム計算は多くの画像処理アプリケーションにおいて一般的な動作である。たとえば、ヒストグラムは、画像中のピクセルの色値の分布を追跡するために使用される。しかしながら、ヒストグラム配列への更新は、配列への入力データに依存して、ランダムでありうる。特に、近隣の要素のインデックスが同じヒストグラム・ビンを指すことがある。この条件のため、複数のデータを並行して（すなわち、SIMDモードで）処理することは非常に難しくなる。]
課題を解決するための手段

[0008] 本発明は、請求項記載の手段によって従来技術の課題を解決する。]
図面の簡単な説明

[0009] Ａは、本発明のある実施形態に基づくプロセッサ・コアのブロック図である。Ｂは、本発明のある実施形態に基づく、収集／分散ユニットの例示的な表現である。
本発明のある実施形態に基づく、原子的なベクトル動作を実行するための流れ図である。
本発明のある実施形態に基づく、システムのブロック図である。]
実施例

[0010] 諸実施形態は、メモリ分散・収集機能を、原子的なベクトル動作のサポートを提供するよう拡張しうる。さまざまな実施形態において、SIMD命令は原子的な動作を可能にするよう提供されうる。特に、SIMD式の複数の非連続的なメモリ位置への原子的動作を効率的にサポートするために、いわゆるベクトル収集‐リンク（gather-linked）命令およびベクトル分散‐条件付（scatter-conditional）命令が提供されうる。本稿での用法では、「ベクトル」および「SIMD」の用語は、単一の命令が複数のデータ要素に作用することを記述するために交換可能に用いられることを注意しておく。このようにして、これらの命令は、SIMD原子的動作が同期プリミティブおよび並列リダクション動作をより効率的に実装することを可能にしうる。さらに、他のベクトル命令が、プロセッサ内リダクション動作およびヒストグラム計算のためのプロセッサ支援を提供しうる。]
[0011] ある実施形態では、収集‐分散ユニットは、原子的なSIMDメモリ動作を許容するよう構成されることができる。データ要素が連続的にではなく間接的に（たとえばA[B[i]]）アクセスされる要素をもつアプリケーションにおいて効率的にSIMDを利用することは、しばしば、データを再配列することを要求し、このことは著しいオーバーヘッドを生じることがある。このオーバーヘッドに対処するため、収集／分散動作を実行するために、SIMD式に非連続的なデータ要素をロードし記憶することを可能にするハードウェア・サポートが提供されることができる。すなわち、収集動作は、ソースSIMDレジスタに含まれる諸アドレスに基づいて、間接的にアドレス指定された諸位置から複数のデータ要素を読み出し（収集し）、それらのデータ要素を単一のSIMDレジスタ中にパックする。逆に、分散動作は、SIMDレジスタ内のそれらの要素をアンパックして、一組の間接的にアドレス指定された位置に書き込む（分散させる）。]
[0012] 具体的には、本発明のある実施形態によれば、収集‐リンク命令は収集される位置についての予約〔リザーブ〕を含み、本発明のある実施形態に基づく分散‐条件付命令は、対応する予約がいまだに保持されている要素へのみ値を分散させる。分散‐条件付はそれらの要素の部分集合についてのみ成功する（あるいはどれについても成功しない）ことがあるので、この命令は、記憶‐条件付〔SC〕の出力に相似して成功または失敗を示す出力マスクを有する。収集‐リンク命令の出力マスクは、ハードウェア実装における、より高い柔軟性を許容しうる。諸実施形態は、スカラーの原子的メモリ動作、すなわちロード・リンク（LL: load-linked）および記憶‐条件付（SC: store-conditional）と呼ばれる一対のスカラー命令を拡張しうる。LLは共有された位置に記憶された値を返し、その位置に関連付けられた予約インジケータをセットする。SCはその予約インジケータをチェックする。予約インジケータが有効であれば、新しい値がその位置に書き込まれ、この動作は成功を返し、有効でなければその値は書き込まれず、この動作は失敗を示すフラグを返す。概念的には、要求される各メモリ位置について、各ハードウェア・コンテキストについて、予約ビットがある。ある共有メモリ位置に関連付けられた諸予約ビットは、その位置が何らかのハードウェア・コンテキストによって書き込まれるときにクリアされる。LLおよびSCの一つの用途は、ロックおよびアンロックのような、より高いレベルの同期プリミティブの実装にある。ロックは、複数のスレッドによる共有データへのアクセスの原子性を保証するために使われる。しかしながら、これらの命令は同時には単一の要素に対してのみ作用する。諸実施形態は、これらの命令のこの限界を克服するために使用されうる。]
[0013] SIMDアーキテクチャでは、VLEN個の位置へのVLEN（SIMDベクトル長）個までの更新が、もし相異なるメモリ位置を更新するとわかっていれば、SIMDを使って並列に実行できる。しかしながら、VLEN個の同時更新の原子性を保証するためには、VLEN個のロックを取得して解放することが必要とされる。スカラー命令が使われる場合、VLEN個のデータ要素を検出、取得、更新してロックを解放するために、ループのVLEN回の逐次反復が実行され、そのような動作にはさまざまなオーバーヘッドが付随する。]
[0014] 多くのアプリケーションにおけるもう一つの一般的な動作は、リダクション動作である。マルチプロセッサ・システムでは、リダクションは、パフォーマンスを改善するために複数のスレッドによって実行されることができる。しかしながら、並列実装では、複数のスレッドが同じメモリ位置を同時に更新するとき、正しさを保証するために、共有されるデータ構造への原子的アクセスが使われる。こうして、リダクション動作は、同時更新の原子性を保証するために、スカラーのロード・リンク命令および記憶‐条件付命令を使用しうる。しかしながら、そのような動作は、本発明の実施形態なしにはSIMD式に実行されることができない。]
[0015] 同期プリミティブおよび並列リダクションの効率的かつSIMDフレンドリーな実装は、さまざまな実施形態において、LL命令およびSC命令へのSIMDサポートを提供することによって実現できる。より具体的には、同期プリミティブおよび並列リダクションのSIMD効率を改善するために、二つの命令、すなわち収集‐リンク（vgatherlink）命令および分散‐条件付（vscattercond）命令がSIMDアーキテクチャのためのロード・リンク動作および記憶‐条件付動作を提供しうる。加えて、SIMDアーキテクチャにおいて利用可能なベクトル収集命令（vgather）およびベクトル分散（vscatter）命令がてこ入れできる。ベクトル収集命令は、次のようなものでありうる：
vgather base, Addr, Dst
これは、VLEN個のデータ要素を、VLEN個（必ずしも連続的でなく、可能性としては重複がある）のメモリ位置から収集させる。それらのメモリ位置のアドレスはbaseおよびAddr（base[Addr[0]],…,base[Addr[VLEN−1]]）から計算され、宛先（destination）Dstに連続的に記憶される。AddrおよびDstはメモリ内、あるいはSIMDレジスタ内のいずれかにあることができる。]
[0016] ベクトル分散命令は次のようなものでありうる：
vscatter base, Addr, Src
この命令は、ソースSrcからのVLEN個の連続的なデータ要素をVLEN個（必ずしも連続的ではないが一意的）のメモリ位置に分散させる。それらのメモリ位置のアドレスは、アドレス・オペランドAddrに記憶されている。vgather命令の場合と同様、AddrおよびSrcはメモリ内またはSIMDレジスタ内のいずれかにあることができる。]
[0017] このように、これら二つのベクトル命令およびスカラーLLおよびSC命令に基づいて、ベクトル収集‐リンク命令vgatherlinkは次のように定義されうる。]
[0018] この命令は、複数のデータ要素を収集してリンクし、また、のちの分散‐条件付命令によって使用されるよう、収集されたデータ要素のメモリ位置を予約する作用をする。このように、この命令は、VLEN個までのメモリ位置memory[Addr[0]],memory[Addr[VLEN−1]]を収集してリンクし、マスクのもとで宛先Dstに入れようとする。データ要素のいくつかを収集してリンクするのに失敗することもありうる。その場合、VLEN個のメモリ位置の部分集合のみを収集してリンクし、マスクFの対応するビットを有効状態、たとえば「1」状態にセットする。失敗した要素はその対応するマスクFを無効状態、たとえば「0」状態にセットする。]
[0019] 同様に、vscattercondは次のように定義されうる。]
[0020] この命令は、複数のデータ要素をメモリに条件付きで分散させる、より具体的には、vgatherlinkによって予約されておりその予約がいまだ有効である（すなわち、vgatherlink以来その位置への書き込みが行われていない）メモリ位置にのみ、分散させる作用をする。このように、この命令は、ソースSrcからのVLEN個までのデータ要素をVLEN個のメモリ位置memory[Addr[0]],…,memory[Addr[VLEN−1]]にマスクFのもとで条件付きで分散させる。個々の分散‐条件付動作が失敗したマスク下のすべての要素について、マスクFの対応する要素は無効状態、たとえば「0」状態にセットされる。]
[0021] vgatherlink命令およびvscattercond命令の組み合わせならびにマスク操作（後述）を使い、VLEN個の原子的動作の部分集合（たとえば、VLEN個のロックの部分集合の取得）が実行でき、対応するマスク要素が1にセットされる。このマスクは、SIMD領域において安全に実行するために使用できる。というのも、成功した原子的動作に対応するマスク下のSIMD要素の部分集合のみが有効にされるからである。ここで表１を参照すると、vgatherlinkおよびvscattercondを使ってVLEN個のロックを取得および解放する例示的なコード・セグメントが示されている。]
[0022] 上記のコードは、すべてのVLEN個の要素が更新されるまで、whileループの逐次反復毎にマスクのもとでVLEN個のSIMD要素の部分集合を更新する。他のスレッドとのロック競合のため、whileループの所与の反復においてはロックが得られないこともありうることを注意しておく。これは、すべての要素が「無効」状態にある場合にマスクのもとで実行されるSIMD_update領域が動作なし（NOP: no operation）としてはたらくことにつながる。マスク下でロックのサブセットのみが取得されるので、ロックのソートは要求されない。ロックのソートは、典型的には、デッドロックを避けるためにクリティカルなセクションの対応するシリアル実装において使用される。ロックのソートは、シリアル実装においては、より複雑で非効率的なコードという代償で、回避できる。上記のコードでは、デッドロックは、競合のないロックのみを取得して実行を進めることによって防止できる。このコードの例示的な実装は、図２に関連して後述する。] 図２
[0023] vgatherlinkおよびvscattercond命令の定義が柔軟であり、種々の使用シナリオを可能にできることを注意しておく。たとえば、上記のコードにおいて、代わりに、すべてのVLEN個のロックが取得されてしまうまでロックを取得するようまず逐次反復し、それからすべてのVLEN個の更新を同時に実行することもできる。]
[0024] スカラーのロード・リンク命令は常に成功する一方、本発明のある実施形態に基づくvgatherlink命令は、アドレスの部分集合において失敗することが許容されることを注意しておく。失敗が起こるには、いくつかの理由がありうる。たとえば：（１）他のスレッドがリンクされるアドレスの部分集合を持っている；（２）キャッシュにおけるコンフリクト：新しいラインを持ち込む唯一の方法が別のリンクされたラインを追い出すことである場合（たとえば、限られた関連付け可能性のため）；（３）ラインがリモート位置またはメモリ内にあり、フェッチするのに長い遅延がかかる（たとえば、キャッシュ・ミスが発生）。]
[0025] 設計者がvgatherlink命令の失敗を許容することを選ぶことのできる他の多くの状況がある。失敗を許容することで、効率を改善しつつ、潜在的に競合の量を減らすことができる。つまり、VLEN個のアドレスについてvgatherlink命令が成功するのを待つことは、競合を増しうる。一方、うまくリンクされたアドレスの部分集合のみにvscattercond命令をすぐ発することは、競合の量を減らす。]
[0026] 上記の議論において、すべてのロック位置が一意的であると想定している。この制約条件は、プログラマーに、whileループにはいる前にロックを一意的なロックの諸部分集合に分割することを強制する。これは潜在的には高価な計算である。たとえば、VLEN個の要素が同時にツリーに挿入されるとき、プログラマーはコンパイル時には、どの要素が一意的であるかを知るすべがないことがありうる。]
[0027] ソフトウェアでロックを一意的な部分集合に分割することは高価であるが、vgatherlinkおよびvscattercond命令の意味内容（semantics）は、分割が必要とされないというものである。これらの命令は、分散‐条件付および通常の分散動作とは、単一のSIMD動作が同じ位置に複数の値を書き込もうとする要素エイリアシング（element aliasing）の扱いにおいて、異なる。エイリアシングされた（aliased）要素更新のうちの一つのみが成功し、出力マスクによって指示される。さまざまな実施形態において、収集‐リンク命令および分散‐条件付命令はいずれも出力マスクをもつので、ハードウェア設計者は、エイリアスの検出および解決を、いずれの命令の一部として実装することを選ぶこともできる。vgatherlinkまたはvscattercond命令はAddr内の一意的なアドレスの部分集合のみを処理するので、これは、whileループの所与の反復において一意的なロックのみが取得され、SIMD_update命令がVLEN個の要素の群内の一意的な諸要素に対してのみ実行されることを保証する。]
[0028] 上記の議論はロック取得に焦点を当ててきたが、vgatherlinkおよびvscattercondは少なくとも一つの他の使用シナリオをもつ。並列リダクション（parallel reductions）である。多くのアプリケーションにおいて、SIMD_update命令は、共有メモリ内の他のオブジェクトにアクセスすることは必要としない。したがって、そのようなオブジェクトは、更新のための原子性を保証するために取得されたロックをもつ必要はない。その代わり、vgatherlinkおよびvscattercond命令は、次の表２のように、更新されているデータに対して使用できる。]
[0029] このコードにおいて、vgatherlink命令は、グローバル・データ構造（glb_data）からベクトル・レジスタV中にデータ要素を収集する。該命令はまた、失敗した収集要素に対応してマスク・レジスタFの諸ビットを0に設定する。SIMD_update命令はベクトル・レジスタVを更新する。次いで、vscattercond命令はベクトル・レジスタVをグローバル・データ構造に分散させ、また、失敗した分散要素に対応してマスク・レジスタFの諸ビットを0に設定する。vscattercond命令ののち、マスク・レジスタFは、この反復工程においてうまく更新された各要素については1を含む。F1との排他的OR（XOR）演算はそれらのマスク・ビットをクリアし、まだ更新されていない要素に対応するマスク中のビットを1に設定する。]
[0030] vgatherlinkおよびvscattercond命令を直接、並列リダクションを実行するために適用することは、いくつかの利点をもたらしうる。まず、ロックを把握して解放する必要がないので、コードはより効率的である（つまり、表２のコードは表１のコードよりずっと短い）。第二に、ロック変数のためにメモリにアクセスする必要がないので、メモリの振る舞いがよりよくなる。]
[0031] 本稿に記載されるベクトル命令は、多くの方法で実装できる。そのような命令は、vgatherlinkおよびvscattercond動作における各要素のための予約位置を含め、さまざまなSIMDハードウェア資源をてこ入れできる。ある実施形態では、32ビット要素当たり１予約位置という粒度が使用されうるが、他の実施形態はより小さなまたはより大きな粒度を有していてもよい。単一の反復工程においてvgatherlink命令が収集し、vscattercondが分散させる要素の数は、設計パラメータであることができる。より多数の要素が収集され、分散されることを許容すればパフォーマンスはよくなるが、より多くの資源が必要となる。]
[0032] ある実施形態では、vgatherlinkおよびvscattercond命令は、それぞれ付録Ｉおよび付録ＩＩに示される外的な振る舞いをもちうる。]
[0033] このように、諸実施形態は、SIMDアーキテクチャにおける原子的な動作の効率的なサポートを提供しうる。このようにして、複数のメモリ位置への原子的なアクセスをシリアル化する必要が、本稿に記載される命令を使って、回避できる。そのような複数位置へのアクセスは、効率的なループ構造、たとえばdo-whileループを使って可能にされる。]
[0034] 前記命令の諸実施形態は、さまざまなアプリケーションにおいて使用されうる。たとえば、ロックの使用のために、記載される命令は、物理シミュレーション・アプリケーションのようなさまざまなアプリケーションにおいて動作を実行するために使用されうる。同様に、リダクション動作のために、記載される命令は、さまざまなアプリケーション、たとえば画像処理アプリケーションおよび疎な線形代数プリミティブを利用するアプリケーションとの関連で使用できる。もちろん、本発明の範囲はこれに関して限定されるものではなく、本稿で記載される命令は他のアプリケーションにおいても使用できる。]
[0035] ここで図１のＡを参照すると、本発明のある実施形態に基づくプロセッサ・コアのブロック図が示されている。図１のＡに示されるように、プロセッサ・コア１０は、コア１０と同様の構成の複数のコアを含むマルチコア・プロセッサの単一のコアであってもよい。図１のＡに示されるように、コア１０は、SIMD動作をサポートするアーキテクチャのものであってもよい。たとえば、パイプライン／機能ユニット２０のさまざまなコンポーネントは、たとえば拡張されたレジスタおよびALUなどのような機能ユニットを介して、ベクトル・サポートを提供するために、拡張されてもよい。] 図１
[0036] 引き続き図１のＡを参照すると、パイプライン／機能ユニット２０は、ロード／記憶ユニット（LSU: load/store unit）３０および収集／分散ユニット（GSU: gather/scatter unit）４０に結合されうる。LSU３０は、キャッシュ・メモリ５０に関してロードおよび記憶命令の実行を扱いうる。キャッシュ・メモリ５０はある実施形態ではレベル１（L1）キャッシュであってもよい。同様に、GSU４０は、本稿に記載されるベクトル収集‐リンク命令およびベクトル分散‐条件付命令のような収集および分散命令の実行を扱いうる。] 図１
[0037] これらのユニットは多くの異なる仕方で構成されうるものの、ここで図１Ｂを参照すると、本発明のある実施形態に基づく収集／分散ユニットの例示的な表現が示されている。図１Ｂに示されるように、GSU４０は制御論理回路４２を含みうる。制御論理４２は、本稿に記載される命令のようなさまざまなベクトル命令の実行を扱うためのさまざまなハードウェア、ファームウェアおよびソフトウェアまたはそれらの組み合わせを含みうる。そのような動作を実現するために、制御論理４２はマスク記憶４４と通信してもよい。マスク記憶４４は、たとえば本稿に記載される種々の命令のための入力マスクおよび／または出力マスクとして使用できるベクトル・マスクの形で、マスク情報の記憶を提供するための一つまたは複数の記憶位置を含みうる。さらに、制御論理４２は、ベクトル記憶４６と通信してもよい。ベクトル記憶４６は、本稿に記載されるさまざまな命令のためのオペランドとして使用されるベクトル・データ要素の記憶を提供するための、ベクトル・レジスタ・ファイルまたは他の一時記憶であってもよい。さらに、制御論理４２によって実装されうる、本稿に記載されるようなベクトル・シャッフル命令に従ってさまざまなデータ要素をシャッフルすることを可能にするよう、シャッフル論理４８が設けられてもよい。さらに図１のＢに示されるように、制御論理４２は今度は、コアの上流の諸部分、たとえば図１のＡのパイプライン／機能ユニット２０ならびにコアの下流部分、たとえばキャッシュ・メモリ５０と通信してもよい。図１のＢの実施形態におけるこの個別的な実装に関して示されているものの、本発明の範囲がこの点に関して限定されないことは理解されたい。] 図１ 図１Ｂ
[0038] ある実施形態では、GSU４０は、ロード・リンク要求を生成してメモリ５０に送るほかは、収集動作と同様にベクトル収集‐リンク動作を扱いうる。同様に、GSU４０は、通常の記憶の代わりに、L1キャッシュへの記憶‐条件付要求を送りうる。さらに、GSU４０は、個々の要求の成功または失敗に基づいてこれらの動作のための出力マスクをアセンブルし、記憶する。]
[0039] ある実施形態では、収集‐リンク命令および分散‐条件付命令をサポートするために、キャッシュ・メモリ５０のキャッシュ・タグ構造が、キャッシュ・ラインごとにいわゆる収集ロード制御記憶（GLSC: gather load control store）エントリーを含みうる。GLSCエントリーは二つのフィールドを含みうる：有効ビットと、ハードウェア・スレッド識別子（ID）（同じコア上の同時のマルチスレッド化された（SMT: simultaneous multithreaded）スレッドの間で区別するための）である。収集‐リンク動作のために、GSU４０がロード・リンク要求をキャッシュ・メモリ５０に送る際、失敗する要求もあれば、成功する要求もある。成功する各要求について、キャッシュは対応するGLSCエントリーを更新し（たとえば、有効ビットがセットされ、要求者のスレッドIDが充填される）、GSU４０は出力マスク中の対応するビットをセットし、GSU４０はデータを宛先レジスタ内に入れる。分散‐条件付動作では、GSU４０は一組の記憶‐条件付（store-conditional）要求をキャッシュ・メモリ５０に送る。個々の記憶‐条件付要求は、対応するGLSCエントリーの有効ビットがセットされており、GLSCエントリー・スレッドIDが要求者のスレッドIDに一致する場合に成功する。ある実施形態では、これは、対応するキャッシュ・ラインが、収集‐リンク動作からの一致するロード・リンク要求によってうまくリンクされて以降、介在する書き込みによって修正されたり追い出されたりしていない場合に真となる。個々の記憶‐条件付要求が成功するとき、キャッシュはGLSC有効フラグをクリアし、キャッシュ・ライン中のデータを修正し、GSU４０は出力マスク中の対応するビットを設定する。]
[0040] ここで図２を参照すると、本発明のある実施形態に従って原子的なベクトル動作を実行するための流れ図が示されている。図２に示されるように、方法１００は、ベクトル・データ要素への原子的な更新を可能にするために、ベクトル収集‐リンク命令およびベクトル分散‐条件付命令を使用しうる。図２の実施形態でのこの個別的な実装をもって示されているものの、本発明の範囲はこれに関して限定されるものではないことを注意しておく。図２に示されるように、方法１００は、ブロック１１０において開始されうる。ここで、ベクトル・マスクが有効状態に設定されてもよく、ベクトル・インデックス情報が取得されてもよい。そのような動作は、入力マスクを有効状態に設定し、SIMDデータ要素のためのインデックスを計算する（すなわちSIMDデータ要素のためのアドレスを得る）ために実行されうる。] 図２
[0041] 次いで制御はブロック１２０に渡される。ここで、すべてのSIMD要素が更新されるまで逐次反復されるループが開始されうる。このループは、ベクトルロック情報を得るためのベクトル収集‐リンク命令を実行することによって始まってもよい。具体的には、この収集‐リンクはこのように、VLEN個までのロック値を得るために使用されてもよい。菱形１２５で判定されるところにより所与のデータ要素について不成功の場合、つまり所与のデータ要素についてロックが利用可能でない場合、制御はブロック１３０に渡され、その利用可能でないロックについての対応するベクトル・マスク・インジケータが無効状態に設定されうる。もしそうではなく所与のロックが利用可能である場合には、そのような利用可能なデータ要素をロックしようとして、ベクトル分散‐条件付命令が実行されうる（ブロック１４０）。ロックを取得するいかなる成功動作についても、ベクトル分散‐条件付命令に関連付けられた出力マスクはセットされたままに留まりうる。一方、取得できなかったそのようないかなるロックについても、該マスクはその代わり、無効状態に設定されうる。次いで制御はブロック１５０に渡され、ここで、SIMD更新がデータ要素の部分集合に対して実行されうる。より具体的には、ブロック１４０でロックが取得されたいかなるデータ要素についても、SIMD更新が実行されうる。次いで制御はブロック１６０に渡され、ここで、更新されたデータ要素をアンロックするためにベクトル分散命令が実行されうる。次いで、菱形１７０において、追加的なベクトル・データ要素が更新されるべく残っているかどうかが判定されうる。もし残っていれば、制御はブロック１２０に戻る。もし残っていなければ、方法１００は完了する。図２の実施形態におけるこの個別的な実装をもって示されているが、本発明の範囲はこれに関して限定されるものではない。] 図２
[0042] 諸実施形態は、さらに、SIMDモードにおける分散リダクション（scatter reductions）を可能にするために使用されうる。諸実施形態は、概念上、分散リダクション動作を三つの動作に分割する。第一に、第一の配列を、SIMD幅に等しい長さのチャンク〔かたまり〕に分ける。この配列は、所与の長さの整数または浮動小数点値の配列、たとえば第一の配列、長さNの値をもついわゆるC配列であってもよい。いわゆるB配列と称されるさらなる配列は長さNの整数インデックス配列であって、その要素は[1…M]の範囲内にあり、C配列の各要素の、長さMの他の配列A上へのマッピングを定義していてもよいことを注意しておく。インデックス（すなわち配列Bの内容）の分布はしばしばランダムであることを注意しておく。さらに、B配列の複数のエントリーは同じ値を有していてもよい。そのことは、C配列の複数の値をA配列の同じ要素に還元〔リダクション〕させる。第二に、各チャンク（SIMDレジスタ内にあると想定される）内で局所的リダクションを実行し、これらの各動作の終わりには、SIMDレジスタは、チャンク内のAの一意的な諸要素に対応する値を保持することになり（すなわち、レジスタ内のどの二つの値も配列の同じ要素に還元される必要はない）、すべての重複する値はこの一意的な要素に還元されている。第三に、各チャンクについて収集‐更新‐分散メモリ動作を実行して、そのチャンクについてのリダクションを完了する。]
[0043] 諸実施形態は、諸レジスタにおいてSIMDリダクションを実行することにおいて支援するさらに別のベクトル命令を提供してもよい。より具体的には、その命令は、第一のSIMDレジスタにおいて一意的な諸項目を見出し、重複している項目についてシャッフル制御（shuffle control）を生成するために使用されうる。そのような動作後は、シャッフル制御は、第一のSIMDレジスタからの第二のSIMDレジスタの生成を、重複する要素の対がそれぞれのSIMDレジスタにおいて対応する位置にあるように行うために使用されることができる。さらに、各対からの対応する重複要素を宛先ベクトル・レジスタに「還元」するために、これら二つのベクトル・レジスタの累積が実行される。シーケンス全体は、残っている要素がすべてAの相異なる要素にマッピングされるようになるまで反復される。このシーケンスは、反復数を最小にするために、各反復工程においてできるだけ多くの重複要素の対を累積する。代替的な諸実施形態は、実装コストを削減するために、重複の対の部分集合のみを累積してもよい。]
[0044] 上記の第二の動作の開始に先立って、配列BおよびCは（第一の動作におけるように）さまざまなチャンクに分割されることができる。それらのチャンクは二つのSIMDレジスタにロードされる（便宜上、これらのレジスタをVbおよびVcと呼ぶ）。第二の動作は、Vbの対応する要素において同じ値をもつVcの諸要素を組み合わせる。この第三の動作を実行するために、Vbの各要素をVbの他の要素に対してシリアルにチェックして何らかの一致があるかどうかを判定するよう、命令のシーケンスが使用されることができる。一致が見出されたら、Vcにおける対応する諸要素は還元される。次の表３はこの第二の動作の擬似コードである。]
[0045] しかしながら、このシリアル実装はO(N2)の計算量をもつ。したがって、本発明の諸実施形態は、この動作の計算量をO(logN)にまで低下させるために、本稿でベクトル・シャッフル・トゥー・リデュース（shuffle-to-reduce）命令と称されるベクトル命令vshuf2reduceを提供してもよい。このVshuf2reduce命令は一つのソースVbおよび入力マスク（どの要素が有効かを示す）を受けて、（スカラー・レジスタにおける）シャッフル制御を生成し、マスク・レジスタを更新する。ある実施形態では、この命令は次のフォーマットをもつ：]
[0046] このように、このvshuf2reduce命令は、Vcについてのシャッフル制御を生成するために、Vb内の諸要素のVb内の他の諸要素に対する全部対全部の比較を実行する。シャッフル制御は、Vc内の諸要素を、Vb内で同じインデックス値をもつVc内の他の諸要素と対ごとの仕方で揃える（line up）ためのシャッフル命令への入力として使われる。さらに、マスクFが返され、このマスクにおいて、各対からの二つの項目の一方に対応する要素が無効に設定されている。]
[0047] 上記の第三の動作は、第二の動作の出力VoutputをCの現在の内容と組み合わせるものである。これは、Voutputに対応するCの要素を読み出し、それらの値をVoutputと一緒に累積し、次いで新たに累積された値をもとのCにおける対応する位置に記憶することを含む。]
[0048] 次の表４は、この命令を使って分散リダクションを実行する擬似コードである。]
[0049] vshuf2reduce命令は、ツリー・リダクション（tree reduction）のためのシャッフル制御を生成する。つまり、whileループは、最悪ケース（すべての要素が同一であり、よって単一の要素に還元される場合）でもO(log(VLEN))ステップ以内に完了することが期待され、上述した分散リダクション動作の第二の動作のパフォーマンスを著しく改善する。Vcのすべての要素がVbの一意的な値をもつ場合には、ループは単一の反復工程において完了しうる。]
[0050] ある実施形態では、vshuf2reduce命令は、表５の次の擬似コードに基づいて実装できる。]
[0051] 全部対全部の要素ごとの比較は、段階的に実装でき、シャッフル制御は、ある実施形態では、事前プログラムされたルックアップ・テーブル〔探索表〕を使うことによって生成できる。]
[0052] 付録ＩＩＩは、スカラー・リダクションの第二の動作のためのこの命令の使用を示している。]
[0053] 諸実施形態は、SIMDレジスタ内の複数のインデックスが同じ場合の効率的な扱いを通じてヒストグラム計算の効率的なSIMD実行を可能にするさらなる命令を提供してもよい。そのような命令は、ソースSIMDレジスタ内の一意的な整数値の分布数計数（population count）を計算してもよい。出力は、一意的な諸要素の分布数計数を保持するSIMDレジスタと、どの要素が一意的であるかを示すマスク・レジスタである。ある実施形態では、vitemcountと称されるこの命令は次のフォーマットをもつ：]
[0054] 動作例として、初期状態を次のようなものとする（ここで、「‐」はどうでもいい値を意味する）：]
[0055] vitemcount命令後、状態は次のようになる。]
[0056] Vsの各要素Vs[i]の分布数計数値はVd[i]に記憶される。Vsにおける一意的なインデックスは、Fmask内にその対応する書き込みマスクがセットされる。]
[0057] このvitemcount命令を用いて、SIMDヒストグラム計算は表６における次のように提供されることができる。]
[0058] 表６に示されるように、この計算は四段階で実行される。第一段階では、ソース・レジスタVsおよびマスクFがベクトル・レジスタ・ファイル（VRF: vector register file）およびマスク・レジスタ・ファイル（RF）からそれぞれ読み込まれる。第二段階では、Vsにおける一意的な要素を同定するために全部対全部の比較が実行される。この第二段階の結果は、Vsの各要素Vs[i]に関連付けられた４ビット・タグであり、二つ以上の同一要素の群が同じタグをもつ。第三のパイプライン段階は、それらの４ビット・タグを使って、同一要素の各群における要素数を計数する。第四段階にして最終段階では、計数ベクトルおよびマスクがVdおよびFにそれぞれ書き込まれる。いくつかの実装では、この命令は、並列なヒストグラム計算を可能にし、シリアル実装に対して高速化を提供できる。]
[0059] 諸実施形態は、多くの異なるシステム種別において実装されうる。ここで図３を参照すると、本発明のある実施形態に基づくシステムのブロック図が示されている。図３に示されるように、マルチプロセッサ・システム５００はポイント・ツー・ポイントの相互接続システムであり、ポイント・ツー・ポイント相互接続５５０を介して結合された第一のプロセッサ５７０および第二のプロセッサ５８０を含む。図３に示されるように、プロセッサ５７０および５８０のそれぞれは、第一および第二のプロセッサ・コア（すなわち、プロセッサ・コア５７１ａおよび５７４ｂならびにプロセッサ・コア５８４ａおよび５８４ｂ）を含むマルチコア・プロセッサであってもよい。各プロセッサ・コアは、本発明の実施形態に基づく単一命令ベクトル動作の実行を可能にするよう、図１のＡおよびＢに示されるような論理を含んでいてもよい。このようにして、原子的なベクトル動作が実行されることができ、本稿に記載されるベクトル命令をてこ入れするためにさまざまなコードが実行されることができる。] 図１ 図３
[0060] 引き続き図３を参照するに、第一のプロセッサ５７０はさらに、メモリ・コントローラ・ハブ（MCH）５７２およびポイント・ツー・ポイント（P-P）インターフェース５７６および５７８を含む。同様に、第二のプロセッサ５８０はさらに、MCH５８２およびP-Pインターフェース５８６および５８８を含む。図４に示されるように、MCH５７２および５８２はプロセッサをそれぞれのメモリ、すなわちメモリ５３２およびメモリ５３４に結合する。メモリ５３２およびメモリ５３４はそれぞれのプロセッサにローカルに取り付けられたメイン・メモリ（たとえば、動的ランダム・アクセス・メモリ（DRAM））の一部であってもよい。第一のプロセッサ５７０および第二のプロセッサ５８０は、チップセット５９０に、それぞれP-P相互接続５５２および５５４を介して結合されてもよい。図３に示されるように、チップセット５９０はP-Pインターフェース５９４および５９８を含む。] 図３
[0061] さらに、チップセット５９０は、チップセット５９０を高性能グラフィック・エンジン５３８と結合するためのインターフェース５９２を含む。また、チップセット５９０は第一のバス５１６にインターフェース５９６を介して結合されてもよい。図３に示されるように、さまざまなI/O機器５１４が、バス・ブリッジ５１８とともに、第一のバス５１６に結合されてもよい。バス・ブリッジ５１８は第一のバス５１６を第二のバス５２０に結合する。さまざまな機器が第二のバス５２０に結合されてもよい。それにはたとえば、キーボード／マウス５２２、通信装置５２６およびディスク・ドライブまたは他の大容量記憶装置のようなデータ記憶装置５２８が含まれる。記憶装置はある実施形態ではコード５３０を含んでいてもよい。さらに、オーディオI/O５２４が第二のバス５２０に結合されてもよい。] 図３
[0062] 諸実施形態はコードで実装されてもよく、命令を記憶している記憶媒体上に記憶されてもよい。該命令は、該命令を実行するようシステムをプログラムするために使うことのできるものである。記憶媒体は、これに限られないが、任意の型のフロッピー（登録商標）ディスク、光ディスク、コンパクトディスクを利用した読み出し専用メモリ（CD-ROM）、書き換え可能型コンパクトディスク（CD-RW）および光磁気ディスクを含むディスク、読み出し専用メモリ（ROM）、動的ランダム・アクセス・メモリ（DRAM）、静的ランダム・アクセス・メモリ（SRAM）のようなランダム・アクセス・メモリ（RAM）、消去可能なプログラム可能型読み出し専用メモリ（EPROM）、フラッシュメモリ、電気的に消去可能なプログラム可能型読み出し専用メモリ（EEPROM）のような半導体デバイス、磁気カードまたは光カード、あるいは電子的な命令を記憶するのに好適な他の任意の型の媒体を含みうる。]
[0063] 本発明は、限られた数の実施形態に関して記述してきたが、当業者は、それから数多くの修正および変形を認識するであろう。付属の請求項は、本発明の真の精神および範囲にはいるあらゆるそのような修正および変形をカバーすることが意図されている。]
[0064] 付録Ｉ]
[0065] ]
[0066] 付録ＩＩ
vscattercondは次の外的振る舞いをもつべきである。]
[0067] ]
[0068] 付録ＩＩＩ
初期状態（「‐」はどうでもいい値を表す）、SC＝Shuffle_Controlはスカラー・オペランドだが、ここでは理解の簡単のためベクトルとして表している。]
[0069] この時点では、Vbの初期値がみな一意的であれば、Fマスクはいまだすべて1である。それは事実上F1マスクと同じであり、whileループ（L4ないしL9）は実行されずに動作２は完了する。この例では、Vbのいくつかの要素が同一なのでFマスクはF1マスクと同じではない。よって、ループ（L4ないしL9）が実行される。]
[0070] L4からL9までの間のループにおいて、vshuf2reduce、vshuffleおよびvaddは、マスクが変化しなくなるまで繰り返しコールされる。マスクが変化しなくなったら、リダクション動作の終わりということである。]
[0071] L9はループしてL4に戻る。FとF1はまだ異なるので、もう一回ループを実行する必要がある。]
[0072] ]
[0073] ]

权利要求:

請求項1
第一のベクトル命令、各アドレスが複数のデータ要素をもつベクトルの対応するデータ要素を有する記憶位置へのアドレスである複数のアドレスおよび前記ベクトルに関連付けられたマスク情報を受け取り、前記マスク情報によって示されるように前記複数のアドレスの各アドレスに対応する記憶位置から取得されたデータ要素をロードし、それらの記憶位置をその後の動作のためにリザーブする論理を有する、プロセッサ。
請求項2
前記論理は、取得が成功しなかったデータ要素のそれぞれに対応する無効インジケータをもって前記マスク情報を更新する、請求項１記載のプロセッサ。
請求項3
前記論理は、取得が成功したデータ要素に対応する、前記複数のデータ要素の部分集合をロードし、リザーブする、請求項２記載のプロセッサ。
請求項4
請求項１記載のプロセッサであって、前記論理は、第二のベクトル命令、各アドレスが前記ベクトルの対応するデータ要素を有する記憶位置へのアドレスである第二の複数のアドレスおよび第二のマスク情報を受け取り、ソース記憶装置からのデータ要素を、前記第二のマスク情報によって示されるように前記第二の複数のアドレスの各アドレスに対応する記憶位置に、その記憶位置がまだリザーブされている場合に、条件付きで書き込む、プロセッサ。
請求項5
前記論理は、もはやリザーブされていなかった記憶位置のそれぞれに対応する無効インジケータをもって、前記第二のマスク情報からの出力マスクを生成する、請求項４記載のプロセッサ。
請求項6
単一の命令に応答して複数のデータ要素に対して動作を実行する単一命令複数データ（SIMD）ユニットと；前記SIMDユニットに前記複数のデータ要素を与えるよう前記SIMDユニットに結合された制御ユニットとを有する装置であって、前記制御ユニットは、第一のマスクのもとで実行される第一のSIMD命令および第二のマスクのもとで実行される第二のSIMD命令に応答して前記複数のデータ要素の少なくともいくつかに対して原子的なSIMD動作が実行されることを可能にする、装置。
請求項7
前記第一のSIMD命令が、前記第一のマスクに対応する入力マスクに従って、第一の諸メモリ位置から前記複数のデータ要素を取得し、前記第一の諸メモリ位置をリザーブする、請求項６記載の装置。
請求項8
前記第二のSIMD命令が、前記第二のマスクに対応する入力マスクに従って、ソース位置からの第二の複数のデータ要素をリザーブされている前記第一の諸メモリ位置に記憶し、前記第一のSIMD命令が前記第二のマスクの生成を引き起こす、請求項７記載の装置。
請求項9
前記制御ユニットが、第二の複数のデータ要素を有する第二のベクトルを比較して、同じ値をもつデータ要素の群を示すシャッフル・コントロールを出力し、一意的でないデータ要素を示すために第三のマスクのインジケータを設定する第三のSIMD命令を前記SIMDユニットが実行することを可能にする、請求項６記載の装置。
請求項10
前記制御ユニットが、第三の複数のデータ要素を有する第三のベクトルの同一の要素の計数値を生成して、各一意的な要素についての計数値を宛先記憶装置に記憶し、さらに各一意的な要素を示す第四のマスクのインジケータを書き込む第四のSIMD命令を前記SIMDユニットが実行することを可能にする、請求項６記載の装置。
請求項11
プロセッサと；前記プロセッサに結合された動的ランダム・アクセス・メモリ（DRAM）とを有するシステムであって、前記プロセッサは、第一のマスクに従って、ベクトルのデータ要素の少なくとも部分集合を、対応する複数の、可能性としては非連続的なソース位置から取得して、前記部分集合の前記可能性としては非連続的なソース位置をその後の動作のためにリザーブする第一の単一命令複数データ（SIMD）命令を実行し、前記データ要素の部分集合を使って原子的なSIMD動作を実行し、第二のマスクに従って、データ要素の少なくとも第二の部分集合を、前記対応する複数の、可能性としては非連続的なソース位置に書き込む第二のSIMD命令を実行する論理を含む、システム。
請求項12
前記プロセッサは、データ要素の前記第二の部分集合を、前記対応する、可能性としては非連続的なソース位置のうちでいまだリザーブされている位置に書き込むよう前記第二のSIMD命令を実行する、請求項１１記載のシステム。
請求項13
前記プロセッサは、取得が成功しなかったデータ要素のそれぞれに対応する無効インジケータをもって前記第一のマスクを更新する、請求項１１記載のシステム。
請求項14
前記プロセッサが、第二の複数のデータ要素を有する第二のベクトルを解析し、同じ値をもつ前記第二の複数のデータ要素の群を示すシャッフル・コントロールを出力し、一意的でないデータ要素を示すために第三のマスクのインジケータを設定する第三のSIMD命令を実行する、請求項１１記載のシステム。
請求項15
前記プロセッサが、第三の複数のデータ要素を有する第三のベクトルの同一の要素の計数値を生成して、各一意的な要素についての計数値を宛先記憶装置に記憶する第四のSIMD命令を実行する、請求項１１記載のシステム。