cnt命令（popcount）

はじめに

• この記事はひとりNEONアドベントカレンダー2020 17日目の記事です
• 昨日はreinterpret命令という、イマイチ何が嬉しいのかわからない命令を紹介した
• 今日はpopcount命令を紹介する

popcountとは

• 特徴量空間の距離、ごちうサーチ 、ハミング距離の計算など、様々な場面で、あるベクトル内の2進数表記での1の数を数えたくなることがある
• 詳細は割愛するが、popcount命令を使うことで、高速に1の数を数えることができ、幸せになれる
• 以下に、popcountの具体例をいくつか紹介

入力	16進数表記	2進数表記	popcountの結果
1	0x0001	b0000000000000001	1
15	0x000f	b0000000000001111	4
16	0x0010	b0000000000010000	1
100	0x0064	b0000000001100100	3
500	0x01f4	b0000000111110100	6
1000	0x03e8	b0000001111101000	6

cnt命令

• 公式リファレンスを見てみると、cnt命令はレジスタ幅の違いを含んでも以下の6種類しか存在しない

vcnt_p8
vcnt_s8
vcnt_u8
vcntq_p8
vcntq_s8
vcntq_u8

• 先程の図でも同じ状況である

• GCCのヘッダarm_neon.hを覗いても状況は同じである

$ grep ^vcnt /usr/lib/gcc/aarch64-linux-gnu/7.5.0/include/arm_neon.h
vcnt_p8 (poly8x8_t __a)
vcnt_s8 (int8x8_t __a)
vcnt_u8 (uint8x8_t __a)
vcntq_p8 (poly8x16_t __a)
vcntq_s8 (int8x16_t __a)
vcntq_u8 (uint8x16_t __a)

• p8型は多項式型なので、ここでは割愛する
• となると引数はint8x8_t、uint8x8_t、int8x16_t、uint8x16_tの4種類しかない
• で、前述の処理を考えると、符号ありだろうと符号なしだろうと、bitの数を数えることには変わりないので、結果として、cnt命令は1種類しかないことになる
• では、例えばint32x4_t型のpopcount処理はどうすれば良いのか？

そこでreinterpret命令ですよ

• と、ここで昨日紹介した、reineterpret命令が効いてくる
• int32x4_t型のpopcountのためには以下のようなコードを書く

    int32_t src[] = {1, 15, 100, 500};
    int32x4_t vsrc = vld1q_s32(src);
    int32x4_t vdst  = vpaddlq_s16(vpaddlq_s8(vcntq_s8(vreinterpretq_s8_s32(vsrc))));

• 演算結果

0:1
1:4
2:3
3:6

• 前述の表と同じ結果が得られている
• 4年前の記事でも触れているが、下図のように、NEONでは、8bitごとのpopcountを求める命令しか存在せず、32bitごとの結果を得るためにはレーン内で水平加算が必要となる

• この様にbit単位で独立している命令は、入力の型がなんだろうと中身の処理は同じ、という命令が存在する
• そのため、reinterpret命令でただのbitの集合と解釈してやれば、1つの命令を使い回すだけで演算が済む
• 8bitより細かくは分けられないので、popcountは8bit単位の結果を返す
  • 32bbitごとに返しちゃうと、それ以上細かい型に適用できないから、最大公約数的なint8x16_tを返すcntq命令1種類だけ実装されている（のだと思う）

おわりに

• 今日は2進数表記でベクトル内の1の数を数えるpopcount命令を紹介した
• 明日も手島の執筆の予定で、固定小数点演算用命令を紹介する予定