Help us understand the problem. What is going on with this article?

POPCOUNTで考えるSIMD

More than 1 year has passed since last update.

立っているビットの数(POPCOUNT)を数える鮮やかな方法があって、簡単なSIMDとなっていました。

どのような方法で計算するか

CPUやJavaなど環境によっては計算ルーチンが用意されていますが、ない時はどのように計算すればいいでしょうか。まずは単純な方法を考えてみます。

1ビットずつ足していく

単純に1ビットずつ見て足していくという方法もありますが、桁数に比例して時間がかかってしまいます。

表引きにする

8ビット分なりを表にすれば加算の回数は減りますが、それでも桁数に比例する状況はそのままとなります。

ということで、これらの方法では桁数比例の時間がかかるのは変わりません1

まずは1ビットの演算なんだし

1ビットずつ足していくとすれば、最初の結果は0~2の2ビットで収まります。なら、何ビットあるか知りませんがレジスタの全幅を使うのは無駄が多すぎます。なお、ビット幅が決まらないと定式化の際に問題が出るので、以下では32ビットとしておきます(いちばん下が0ビット、いちばん上が31ビット)。

0ビット目+1ビット目の結果を0ビット~1ビットの2桁に、2ビット目+3ビット目の結果を2ビット~3ビットに…というように2桁ごとに別々な計算をするようにすれば、一気に16ビットの足し算が終わってしまいます。おまけに、結果の境界を超えた繰り上がりが発生しないので、単なる整数演算でこの演算を行うことができます。

C言語で書けば、val = (val & 0x55555555) + ((val >> 1) & 0x55555555)のようになります(0x55555555は、1ビットおきに値を拾うためのマスクです)。

あとは同様に、2桁+2桁の足し算、4桁+4桁の足し算というようにすすめていけば、桁数の対数のステップで終わらせることができます。

SIMDって?

3DCGなどのマルチメディア分野で顕著に見られますが、「大量のデータに同じ演算を行う」必要はよくあります。今回はたまたまふつうの整数演算で片付きましたが、現代のCPUやGPUには、長いレジスタに複数のデータを突っ込んで、複数の演算を並列で一気に行う、SIMD命令が搭載されています。


  1. 桁数にかかわらず整数どうしの演算は定数時間でできる、という前提です(多倍長演算で足し算も桁数に比例する時間がかかる、ような場合は考慮していません) 

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
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  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
ユーザーは見つかりませんでした