SIMDに興味があり、このユースケースを処理できるかどうか疑問に思っています。
[0x018A、0x004B、0x01C0、0x0234、0x0098、0x0343、0x0222、0x0301、0x0398、0x0087、0x0167、0x0389、0x03F2、0x0034、0x0345、...]のような2048個の整数の配列があるとします。
それらがすべて0x00、0x01、0x02、または0x03のいずれかで始まることに注意してください。それらを4つの配列に分割したい:
私は次のようなコードがあると思います:
int main() {
uint16_t in[2048] = ...;
// 4 arrays, one for each category
uint16_t out[4][2048];
// Pointers to the next available slot in each of the arrays
uint16_t *nextOut[4] = { out[0], out[1], out[2], out[3] };
for (uint16_t *nextIn = in; nextIn < 2048; nextIn += 4) {
(*** magic simd instructions here ***)
// Equivalent non-simd code:
uint16_t categories[4];
for (int i = 0; i < 4; i++) {
categories[i] = nextIn[i] & 0xFF00;
}
for (int i = 0; i < 4; i++) {
uint16_t category = categories[i];
*nextOut[category] = nextIn[i];
nextOut[category]++;
}
}
// Now I have my categoried arrays!
}
私の最初の内部ループはSIMDを必要とせず、単なる命令である可能性(x & 0xFF00FF00FF00FF00)
があると思いますが、その2番目の内部ループをSIMD命令にできるかどうか疑問に思います。
私が行っているこの「分類」アクションのためのSIMD命令のようなものはありますか?
「挿入」の手順はやや有望に思えますが、https://software.intel.com/en-us/node/695331の説明を理解するには少し環境に配慮しています。
そうでない場合、何かが近づいていますか?
ありがとう!
SIMDを使用してそれを行うことができますが、その速度は、使用可能な命令セットと、実装がどれだけ賢いかによって異なります。
1つのアプローチは、配列を取得して「ふるいにかけ」、異なるバケットに属する要素を分離することです。たとえば、16個の16ビット要素を持つ配列から32バイトを取得します。いくつかのcmpgt
手順を使用して、各要素が00 + 01
バケットに分類されるかバケットに分類されるかを決定するマスクを取得し02 + 03
ます。次に、ある種の「圧縮」または「フィルター」操作を使用して、マスクされたすべての要素をレジスターの一方の端に連続して移動し、マスクされていない要素についても同じように移動します。
次に、整理するために、この1以上の時間繰り返して00
から01
や02
からを03
。
AVX2を使用すると、「圧縮」操作のインスピレーションを得るために、この質問から始めることができます。AVX512を使用すると、このvcompress
命令を使用して支援することができます。これは正確にこの操作を実行しますが、32ビットまたは64ビットの粒度でのみ実行されるため、少なくともベクトルごとにいくつか実行する必要があります。
N個のベクトルをロードし、それらを交換して0番目のベクトルの要素が最小になるようにする垂直アプローチを試すこともできます。この時点で、圧縮段階にさらに最適化されたアルゴリズムを使用できます(たとえば、十分な数のベクトルを垂直方向に並べ替えます。最後のベクトルは完全に0x00
etcで始まる場合があります)。
最後に、ソースで、または前処理ステップとして、データを別の方法で編成することも検討できます。つまり、ペイロードバイトから常に0〜3である「カテゴリ」バイトを分離します。処理ステップの多くはどちらか一方でのみ実行する必要があるため、それらをそのように分割することで効率を高めることができる可能性があります。たとえば、すべてのカテゴリである32バイトに対して比較操作を実行してから、32ペイロードバイトに対して圧縮操作を実行できます(少なくとも、各カテゴリが一意である最後のステップで)。
これにより、「カテゴリ」バイトが暗黙的に含まれる16ビット要素ではなく、バイト要素の配列が生成されます。データサイズを半分に削減しました。これにより、将来データで実行したい他のすべての処理が高速化される可能性があります。
この形式でソースデータを生成できない場合は、ペイロードを適切なバケットに配置するときにタグバイトを削除する機会としてバケットを使用できるため、出力はuint8_t out[4][2048];
です。pshufb
コメントで説明されているように、バイトシャッフルを使用してSIMD左パックを実行している場合は、ペイロードバイトのみを下位半分にパックするシャッフル制御ベクトルを選択できます。
(AVX512BWまで、x86 SIMDには可変制御ワードシャッフルがなく、バイトまたはdwordのみであるため、ペイロードバイトを最下部にパックすると同時に、ペイロードをタグから簡単に分離できるバイトシャッフルがすでに必要でした。 )
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加