Loading article…
ギャザー/スキャッターは、複数の任意のインデックスから一度にデータを収集（ギャザー）したり、複数の任意のインデックスにデータを格納（スキャッター）したりするメモリアドレッシングの一種です。使用例としては、スパース 線形代数演算、[1] 、ソートアルゴリズム、高速フーリエ変換、[2]、一部の計算グラフ理論の問題などがあります。[3]これはレジスタ間接アドレッシングのベクトル版であり、ギャザーではインデックス付きの読み取りが、スキャッターではインデックス付きの書き込みが行われます。ベクトルプロセッサ（およびCPUの一部のSIMDユニット）には、多くの入出力システムと同様に、ギャザー操作とスキャッター操作のハードウェアサポートがあり、大きなデータセットをより迅速にメインメモリに転送できます。
この概念は、スキャッターギャザー I/O とも呼ばれるベクトル I /Oに多少似ています。このシステムは、連続した構造からの複数のデータソースを読み取りまたは書き込み用の単一のストリームにマッピングするために使用されるという点で異なります。一般的な例は、ほとんどのプログラミング言語では別々のメモリ位置に格納される 一連の文字列を書き出すことです。
定義
集める
空でない要素を持つ疎なベクトルは、 長さ の 2 つの密なベクトルで表すことができます。は の空でない要素を含み、の要素が配置されているのインデックスを与えます。を に集める は、がすでに計算されているに代入します。 [4] x[]、y[]、idx[] の間にポインタエイリアシングがないと仮定すると、 C実装は次のようになります。
i = 0 ; i < N ; ++ i )の場合x [ i ] = y [ idx [ i ] ];
散らばる
で示されるスパース散布は逆の操作です。 の値を、スパースに分布するベクトル 内の対応する位置、つまりにコピーします。
i = 0 ; i < N ; ++ i )の場合、y [ idx [ i ] ] = x [ i ] となります。
サポート
スキャッター/ギャザーユニットは、ほとんどのベクトルコンピュータ、特にCray-1の一部でもありました。この場合、その目的は、ベクトルレジスタの限られたリソースに値を効率的に保存することでした。たとえば、Cray-1には8つの64ワードベクトルレジスタがあり、加算のゼロなど、結果に影響を与えない値を含むデータは、より有効に活用できる貴重なスペースを消費していました。ゼロ以外の値をレジスタに集め、結果をスキャッターして戻すことで、レジスタをより効率的に使用でき、パフォーマンスが向上しました。このようなマシンは、通常、スキャッター/ギャザーと「ストライド」の2つのアクセスモデルを実装しており、後者は連続したデータをすばやくロードするように設計されていました。[5]この基本的なレイアウトは、特に日本製のさまざまなモデルで、後のスーパーコンピュータの設計 に広くコピーされました。
1990 年代にマイクロプロセッサの設計が改良されるにつれて、コモディティ CPU にベクトル処理ユニットが追加され始めました。当初は単純なものが多く、CPU の汎用レジスタをオーバーレイすることもありましたが、時が経つにつれて、高性能なシステムへと進化し、ハイエンド スーパーコンピュータのユニットに匹敵し、さらにはそれを凌駕するようになりました。この頃までに、これらの設計の多くにスキャッター/ギャザー命令が追加されていました。
AVX2命令セットをサポートするx86-64 CPUは、ベースアドレスからのメモリオフセットを使用して32ビットおよび64ビットの要素を収集できます。2番目のレジスタは、特定の要素がロードされているかどうかを決定し、マスクされた要素による無効なメモリアクセスから発生する障害は抑制されます。[6] : 503–4 AVX -512命令セットには、（潜在的にマスクされた）スキャッター操作も含まれています。[6] : 539 [7] ARM命令セットのスケーラブルベクター拡張には、 8、16、32、64ビットの要素に対するギャザー操作とスキャッター操作が含まれています。[8] [9] InfiniBandは、ギャザー/スキャッターのハードウェアサポートを備えています。[10]
命令レベルのギャザー/スキャッターがなければ、効率的な実装では、例えばプリフェッチなどにより最適なパフォーマンスを得るためにチューニングが必要になる場合があります。OpenMPIなどのライブラリがそのようなプリミティブを提供する場合があります。[2] [8]
参照
参考文献
- ^ Lewis, John G.; Simon, Horst D. (1988 年 3 月 1 日)。「ハードウェア ギャザー/スキャッター がスパース ガウス消去法に与える影響」。SIAM Journal on Scientific and Statistical Computing。9 ( 2): 304–311。doi : 10.1137/0909019。
- ^ ab He, Bingsheng; Govindaraju, Naga K.; Luo, Qiong; Smith, Burton (2007). 「グラフィック プロセッサでの効率的な収集および分散操作」。2007 ACM/IEEE スーパーコンピューティング会議の議事録( PDF)。pp. 1–12。doi : 10.1145/1362622.1362684。ISBN 9781595937643.S2CID 2928233 。
- ^ Kumar, Manoj; Serrano, Mauricio; Moreira, Jose; Pattnaik, Pratap; Horn, WP; Jann, Joefon; Tanase, Gabriel (2016 年 9 月)。「大規模グラフ分析のためのスキャッターギャザー操作の効率的な実装」。2016 IEEE ハイパフォーマンスエクストリームコンピューティングカンファレンス (HPEC)。pp. 1–7。doi : 10.1109 / HPEC.2016.7761578。ISBN 978-1-5090-3525-0. S2CID 10566760。
- ^ BLAS 技術フォーラム標準、第 3 章: スパース BLAS。
- ^ Bell, Gordon (1998年1月25日). A Seymour Cray Perspective (技術レポート).
- ^ ab Kusswurm, Daniel (2022). C++ とアセンブリ言語による最新の並列プログラミング: AVX、AVX2、AVX-512 を使用した X86 SIMD 開発。Apress Media。ISBN 978-1-4842-7917-5。
- ^ Hossain, Md Maruf; Saule, Erik (2021年8月9日). 「AVX-512命令のグラフ分割問題への影響」.第50回国際並列処理会議ワークショップ. pp. 1–9. doi :10.1145/3458744.3473362. ISBN 9781450384414. S2CID 237350994。
- ^ ab Zhong, Dong; Shamis, Pavel; Cao, Qinglei; Bosilca, George; Sumimoto, Shinji; Miura, Kenichi; Dongarra, Jack (2020 年 5 月)。「Arm スケーラブル ベクトル拡張機能を使用した OPEN MPI の最適化」( PDF )。2020年 20 回 IEEE/ACM 国際クラスター、クラウド、インターネット コンピューティング シンポジウム (CCGRID)。pp. 222–231。doi :10.1109/CCGrid49817.2020.00-71。ISBN 978-1-7281-6095-5. S2CID 220604878。
- ^ 「スケーラブルベクター拡張とは?」ARM Developer . 2022年11月19日閲覧。
- ^ Gainaru, Ana; Graham, Richard L.; Polyakov, Artem; Shainer, Gilad (2016 年 9 月 25 日)。「InfiniBand ハードウェアの Gather-Scatter 機能を使用して MPI All-to-All を最適化する」。第23 回ヨーロッパ MPI ユーザー グループ会議の議事録。pp. 167–179。doi : 10.1145 /2966884.2966918。ISBN 9781450342346.S2CID 15880901 。