スワー

レジスタ内SIMD（SWAR ）は、「パックSIMD」 [ 1 ]とも呼ばれ、プロセッサレジスタに格納されたデータに対して並列演算を実行する技術です。SIMDは「Single Instruction, Multiple Data（単一命令、複数データ）」の略です。

現代の汎用コンピュータプロセッサの多くは、SIMDのための機能を備えており、レジスタ群とそれらを活用するための命令群が存在します。SWARとは、SIMD演算に特化して設計された専用の処理エンジンではなく、これらのレジスタと命令群を利用することを意味します。また、当時はSIMD演算には対応していなかった汎用レジスタと命令群を、様々な斬新なソフトウェアトリックを用いてSIMD演算に使用することもSWARの用語です。[ 3 ]

SWARアーキテクチャ

SWARアーキテクチャとは、レジスタの独立したサブワードまたはフィールドに格納されたデータに対して並列処理を実行することを明示的に意図した命令を含むアーキテクチャです。SWAR対応アーキテクチャとは、その目的を明示的に意図した命令がアーキテクチャに含まれていなくても、これらのフィールドに格納されたデータを独立して処理するのに十分な命令セットを含むアーキテクチャです。

歴史的な初期例の一つは、1958年に運用開始されたリンカーン研究所のTX-2です。これは36ビット幅のメモリを搭載し、ALU内で36ビット1つ、18ビット2つ、あるいは9ビット4つのサブワードを演算する命令群を備えていました。TX -2はSIMDという用語が発明されるよりも古いものです。[ 4 ]

SWARアーキテクチャの初期のよく知られた例としては、MMX拡張セットを実装したMMX搭載のIntel Pentiumが挙げられます。一方、 Intel Pentiumにはそのような命令は含まれていませんでしたが、慎重なハンドコーディングやコンパイラ技術を用いることで、SWARアーキテクチャとして動作させることができました。

初期のSWARアーキテクチャには、DEC Alpha MVI、Hewlett-PackardのPA-RISC MAX、Silicon Graphics IncorporatedのMIPS MDMX、SunのSPARC V9 VISなどがある。MMXと同様に、SWARの命令セットの多くは、より高速なビデオコーディングを目的としている。[ 5 ]

SWARプログラミングモデルの歴史

ウェズリー・A・クラークは1950年代に分割サブワードデータ演算を導入しました。これはSWARの非常に初期の前身と言えるでしょう。レスリー・ランポートは1975年に 「フルワード命令による複数バイト処理」 [ 6 ]と題した論文でSWARの技術を発表しました。

1996年にIntelがMMXマルチメディア命令セット拡張を導入したことで、SIMD並列処理機能を備えたデスクトッププロセッサが普及しました。当初、これらの命令は手書きのアセンブリコードでしか使用できませんでした。

1996年秋、ハンク・ディーツ教授はパデュー大学電気・コンピュータ工学部で学部生向けのコンパイラ構築コースの講師を務めていました。このコースでは、ディーツ教授は学生たちにMMXをターゲットとしたシンプルなコンパイラを構築する一連のプロジェクトを課しました。入力言語は、MasParのMPLのサブセット方言であるNEMPL（Not Exactly MPL）でした。

学期の途中で、コースのティーチングアシスタントであるランドール（ランディ）・フィッシャーは、MMXにNEMPLコンパイラのバックエンドの構築を困難にするいくつかの問題があることに気づきました。例えば、MMXには16ビットデータの乗算命令はありますが、8ビットデータの乗算命令はありません。NEMPL言語はこの問題を考慮しておらず、プログラマーは8ビット乗算を必要とするプログラムを書くことができました。

SIMDのような並列命令を搭載したアーキテクチャは、Intelのx86アーキテクチャだけではありませんでした。SunのVIS、SGIのMDMX 、その他のマルチメディア命令セットは、いわゆるニューメディアアプリケーションをサポートするために、他社の既存の命令セットアーキテクチャに追加されました。これらの拡張機能は、データの精度とサポートされる命令の種類に大きな違いがありました。

ディーツとフィッシャーは、対象アーキテクチャの詳細を知らなくてもモデルをターゲットとしたプログラミングを可能にする、明確に定義された並列プログラミングモデルのアイデアの開発に着手しました。このモデルはフィッシャーの博士論文の基礎となりました。「SWAR」という頭字語は、ある日、パーデュー大学のMSEEビルにあるハンクのオフィスでディーツとフィッシャーによって造られました。[ 7 ] これは、この形式の並列処理、この種の処理をネイティブに実行するように設計されたアーキテクチャ、そしてフィッシャーの博士論文である汎用プログラミングモデルを指します。

これらの多種多様なアーキテクチャ向けのコンパイルの問題は、LCPC98で発表された論文で議論されました。[ 5 ]

SWARのいくつかの応用

SWAR処理は、画像処理、 [ 8 ] 、暗号ペアリング、[ 9 ] 、 ラスター処理、[ 10 ] 、数値流体力学、[ 11 ] 、通信などで利用されている 。[ 12 ]

例

SWAR技術は、特別なハードウェアサポートのないシステムでも使用できます。 論理演算はビット単位で行われるため、レジスタの各ビットは独立して処理されます。加算と減算の使用はより複雑ですが、レーン間の不要なキャリー伝播を回避するように注意すれば有用です。このキャリー伝播を除けば、64ビットの加算または減算1回は、8ビットの加算または減算8回を実行するのと同じです。

カウントビットセット

SWAR技術の典型的な例は、レジスタの（セットされているビットの数）のポピュレーションカウントを求めることでしょう。レジスタは、1ビット、2ビット、4ビットなどのフィールドの連続として扱われます。

まず、1ビットフィールドの人口カウントは、単にフィールド自体であることに注意してください。2ビットフィールドの人口カウントを求めるには、それを構成する2つの1ビットフィールドの人口カウントを合計します。これは、64ビット値内の32個の2ビットフィールドに対して並列に実行できますx。 

x2 := (x & 0x5555555555555555) + ((x >> 1) & 0x5555555555555555);

16進定数は2進0x5数の0101 2で、偶数ビットを分離します。加算の最大値は2であるため、各2ビットフィールドをオーバーフローさせることはできません。

これを繰り返すことで、2ビットフィールドを4ビットフィールドに結合できます。ここでは、2進数で0011 2 、つまり16進数で0011 20x3のマスクを使用して、ビットのペアを分離します。 

x4 := (x2 & 0x3333333333333333) + ((x2 >> 2) & 0x3333333333333333);

これで、各 4 ビット フィールドに 0 から 4 までのカウントが含まれます。4 ビット フィールドには最大 15 の値を格納できるため、2 つの 4 ビット人口カウントを加算してもオーバーフローは発生せず、加数ごとに 1 回ではなく、加算 後にマスクを実行できます。

x8 := (x4 + (x4 >> 4)) & 0x0f0f0f0f0f0f0f0f;

この時点で、8 ビット フィールドは最大 255 の値を保持できるため、最後までさらにマスクする必要はありません。 

x16 = x8 + (x8 >> 8); x32 = x16 + (x16 >> 16); x64 = x32 + (x32 >> 32); 人口カウント = x64 & 0xff;

さらなる改良

これにはよく知られたバリエーションがいくつかあります。特に、最後の3つのシフトと加算のステップを組み合わせると、 

人口数 = (x8 * 0x0101010101010101) >> 56;

シフトと加算の3段階の処理には6つの命令が必要であり、各命令は前の命令のデータに依存するため、少なくとも6クロックサイクルかかります。乗算は通常、より高速に実行できます。32ビットワードを処理する場合は、乗算に3サイクルかかるのが一般的であるため、この説明は明確ではありません。

2つ目のバリエーションは、最初のステップを変更するものです。各2ビットフィールドの2つのビットb 1とb 0を加算するのではなく、2ビットフィールドの初期値を 2 b 1 + b 0とします。この値からb 1を減算すると、マスク演算を1回行うだけで、目的の合計が得られます。 

x2 := x − ((x >> 1) & 0x555555555555555);

ゼロバイトを見つける

文字列中のヌル終端文字を検索するのは一般的です。64ビットプロセッサは一度に8バイトを処理できるため、これを1バイトずつ行うのは非効率的です。

同じ手法を使用して、まずターゲットバイト値と 排他的論理和をとることで、パス名区切り文字やその他の区切り文字を検索することもできます。

一部のアーキテクチャには、8バイトの比較を一度に実行するための特別な命令が含まれています。例えば、DEC Alphaには8バイトの比較を一度に実行する命令が含まれていましたCMPBGE。ただし、ゼロバイトの検索は特別なサポートなしで実行できます。

1 つの方法は、上記のビットカウントの例とほぼ同じように 8 ビットを OR結合することです。

x2 = x | x<<1; x4 = x2 | x2<<2; x8 = x4 | x4<<4; バイトマップ = ~x8 & 0x8080808080808080;

この結果、byte_map元々ゼロであったバイトの最上位ビットに 1 ビットが付くことになります。

しかし、算術演算を用いたキャリー伝播を利用することで、より高速に処理できます。各バイトに0x7f（2進数01111111 2）を加算すると、下位7ビットが0でない場合、ビット7にキャリーが発生します。課題は、キャリー伝播がビット7で停止し、他のバイトに影響を与えないようにすることです。これは、各バイトの下位7ビットと上位ビットを個別に処理することで実現できます。まず、加算する前に、以下の論理積をとって各バイトの下位7ビットを抽出します。 0x7f0x7f

x7 = (x & 0x7f7f7f7f7f7f7f7f) + 0x7f7f7f7f7f7f7f7f;

次に、最上位ビットと結合します。 

x8 = x7 | x;

この値は、各8ビットフィールドのmsbitが、そのバイトが0以外の場合、1に設定されます。最後に： 

バイトマップ = ~(x8 | 0x7f7f7f7f7f7f7f7f);

は各バイトの不要な下位ビットをすべてセットし、その後すべてを補数化して、対応する入力バイトが0の箇所に1のビットのみを残します。（これは と同じです~x8 & 0x80...80が、同じ定数値を使用します。）1のビットがない場合、次の単語に検索を続行できます。1のビットがある場合、その位置から文字列の長さを計算できます。

さらなる改良

リトルエンディアンプロセッサで最初のゼロバイトを見つけることだけを目的とすれば、 2つの異なる定数を使うことで、より少ない操作で最下位のゼロバイトを見つけることができる。 [ 13 ]

x7 = x − 0x0101010101010101; バイトマップ = x7 & ~x & 0x8080808080808080;

各バイトbについて、 b − 1byte_mapの msbitが設定されていて、 bの msbit がクリアされている場合、その msbit が設定されます。これは、 b = 0 の場合にのみ発生します。

上記のステートメントは、に借入がない場合にのみ真です。借入がある場合は、b = 1 の場合でも条件は真になります。ただし、このような借入は下位のゼロ バイトによってのみ生成されるため、最下位のゼロ バイトは期待どおりに正しく識別されます。

これにより、1つのバイナリ演算が節約されるだけでなく、すべてのバイナリ演算が順番に依存していないため、「AND NOT」（ビットクリア）命令が存在すると仮定すると、2サイクルで実行できます。

小さなテーブル検索

ビットマップの一般化として、非常に小さなルックアップテーブルを1つのレジスタに格納することが可能です。例えば、月の日数は28日から31日までの4つの値の範囲で変化します。これは12×2 = 24ビットで格納できます。 

days_table = 0xeefbb3 + (is_leap_year << 2); days_in_month = 28 + (days_table >> 2*month & 3);

(これは0 ベースの月番号を想定しています。 をシフトすることで 1 ベースの月番号に対応できますdays_table。)

表が 1 つのレジスタにきちんと収まるため、閏年の変更も簡単です。

参照

参考文献

  1. ^ Miyaoka, Y.; Choi, J.; Togawa, N.; Yanagisawa, M.; Ohtsuki, T. (2002).パックドSIMD型命令を用いたプロセッサコア合成のためのハードウェアユニット生成アルゴリズム. Asia-Pacific Conference on Circuits and Systems. Vol. 1. pp.  171– 176. doi : 10.1109/APCCAS.2002.1114930 . hdl : 2065/10689 .
  2. ^ Flynn, Michael J. (1972年9月). 「いくつかのコンピュータ組織とその有効性」(PDF) . IEEE Transactions on Computers . C-21 (9): 948– 960. doi : 10.1109/TC.1972.5009071 .
  3. ^ Fisher, Randall J (2003).レジスタ内の汎用SIMD：民生用マイクロプロセッサにおける並列処理(PDF) (Ph.D.). パデュー大学.
  4. ^ 「アーカイブコピー」（PDF） 。2021年4月22日時点のオリジナル（PDF）からのアーカイブ。{{cite web}}: CS1 maint: アーカイブされたコピーをタイトルとして (リンク)
  5. ^ a b Fisher, Randall J.; Henry G. Dietz (1998年8月). S. Chatterjee; JF Prins; L. Carter; J. Ferrante; Z. Li; D. Sehr; P.-C. Yew (編). 「レジスタ内でのSIMDコンパイル」.第11回並列計算のための言語とコンパイラに関する国際ワークショップ議事録.
  6. ^ランポート、レスリー（1975年8月）. 「フルワード命令による複数バイト処理」 . Communications of the ACM . 18 (8): 471– 475. doi : 10.1145/360933.360994 . S2CID 1593593 . 
  7. ^ディーツ、ハンク。「集約マジックアルゴリズム」。
  8. ^パドヴァ、フラヴィオLC;ペレイラ、ギリェルメ AS;ネト、ホセ・P・デ・ケイロス。カンポス、マリオFM。フェルナンデス、アントニオ O. (2001 年 1 月)。命令レベル並列処理による大きな画像の処理時間の改善(PDF)。チリコンピューティングウィーク、並列分散システムに関するワークショップ V。プンタ・アレナス。2007 年 2 月 25 日にオリジナル(PDF)からアーカイブされました。2012 年 12 月 5 日に取得。
  9. ^ Grabher, Philipp; Johann Großschädl; Dan Page (2009). 「暗号ペアリングのソフトウェア並列実装について」.暗号技術の特定分野. コンピュータサイエンス講義ノート. 第5381巻. pp.  35– 50. doi : 10.1007/978-3-642-04159-4_3 . ISBN 978-3-642-04158-7。
  10. ^ Persada, Onil Nazra; Thierry Goubier (2004年9月12日～14日). 「GRASSにおける細粒度および粗粒度並列処理によるラスター処理の高速化」FOSS/GRASSユーザーズカンファレンス2004議事録.
  11. ^ Hauser, Thomas; TI Mattox; RP LeBeau; HG Dietz; PG Huang (2003年4月). 「複雑なマイクロプロセッサのコード最適化とCFDソフトウェアへの適用」. SIAM Journal on Scientific Computing . 25 (4): 1461– 1477. doi : 10.1137/S1064827502410530 . ISSN 1064-8275 . 
  12. ^ Spracklen, Lawrence A. (2001). SWARシステムと通信アプリケーション(PDF) (Ph.D.). アバディーン大学.
  13. ^ Fisher, James (2017年1月24日). 「ビット演算を使ってC言語でゼロバイトを素早くチェックする」. 2024年12月21日閲覧。
「 https://en.wikipedia.org/w/index.php?title=SWAR&oldid=1319615663」から取得