Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

simd sortで、bubble sort と quadsort で比較してみると?

More than 1 year has passed since last update.

bubble sortと比較してみる。

基本的に今回比較したいのは「条件分岐を使わずに、simd でソートできること」なので、quick sortとかのアルゴリズムは適応対象外にしかならない(仕方がない)。

ということで、バブルソートベースとも比較してみる。

バブルソートの場合、交換回数は28回。
1回の交換が、MAXとMINで処理する必要があるので、
56 instructionが必要になる。

quadsortを使えば、ちょっとだけ命令数を少なくできるかも?

あと、バブルソートの場合、「直前に入れ替えた要素を対象」にすると、スループットとレイテンシーで性能が十分にでないかもしれない。

追記

違う違う。2要素交換に必要なのは、3インストラクションですね……

だから、28回✕3 = 84 instruction ……

quadsortっぽい何かで組んだ方が早い?

        #define SWAP2(valA,valB) \
        { \
                tmp0 = valA \
                valA = _mm256_min_epi32 ( valA, valB ); \
                valB = _mm256_max_epi32 ( tmp0, valB ); \
        }

SWAP2(val0,val1); // step.1-1
SWAP2(val1,val2); // step.1-2
SWAP2(val2,val3); // step.1-3
SWAP2(val3,val4); // step.1-4
SWAP2(val4,val5); // step.1-5
SWAP2(val5,val6); // step.1-6
SWAP2(val6,val7); // step.1-7 val7 is fixed.

SWAP2(val0,val1); // step.2-1
SWAP2(val1,val2); // step.2-2
SWAP2(val2,val3); // step.2-3
SWAP2(val3,val4); // step.2-4
SWAP2(val4,val5); // step.2-5
SWAP2(val5,val6); // step.2-6 val6 is fixed.

SWAP2(val0,val1); // step.3-1
SWAP2(val1,val2); // step.3-2
SWAP2(val2,val3); // step.3-3
SWAP2(val3,val4); // step.3-4
SWAP2(val4,val5); // step.3-5 val5 is fixed.

SWAP2(val0,val1); // step.4-1
SWAP2(val1,val2); // step.4-2
SWAP2(val2,val3); // step.4-3
SWAP2(val3,val4); // step.4-4 val4 is fixed.

SWAP2(val0,val1); // step.5-1
SWAP2(val1,val2); // step.5-2
SWAP2(val2,val3); // step.5-3 val3 is fixed.

SWAP2(val0,val1); // step.6-1
SWAP2(val1,val2); // step.6-2 val2 is fixed.

SWAP2(val0,val1); // step.7-1 val0 and val1 are fixed.

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away