ビット演算の話 / Let's play with bit operations

ビット演算の基礎と応用例の紹介

Transcript

1. 1 37 ビット演算の話 慶應義塾大学理工学部物理情報工学科 渡辺宙志 2024/09/24 研究室ミーティング
2. 2 37 ビット演算とは ビット列同士の論理演算を駆使して計算の高速化を図ること ビット演算の説明 ビット演算の応用例1：イラストロジック ビット演算の応用例2：数独 ビット演算の応用例3：Directed Percolation 今日話すこと
3. 3 37 真偽値とは 真(True)か偽(False)のどちらかの値をとる変数 Pythonの場合 多くのプログラム言語に真偽値を表現する型がある a = bool(1) print(a) # => True type(a) # => bool b = bool(0) print(b) # => False 整数の1をbool型に変換するとTrueに、0はFalseになる type(1 < 2) # => bool 比較結果はbool型になる (if文やwhile文などの条件分岐に使う)
4. 4 37 論理演算 論理演算とは真偽値に関する演算のこと 否定 (NOT) 「真」の否定 → 偽 「偽」の否定 → 真 print(not True) # => False print(not False) # => True 真偽値をひっくり返す Pythonコード例
5. 5 37 論理演算 論理積 (AND) 「A and B」は「A かつ B」の意味 AとBがどちらも真の時にのみ真、それ以外は偽 print(True and True) # => True print(True and False) # => False print(False and True) # => False print(False and False) # => False Pythonコード例
6. 6 37 論理演算 論理和 (OR) 「A or B」は「A または B」の意味 AとBのどちらかが真の時にのみ真、それ以外は偽 print(True or True) # => True print(True or False) # => True print(False or True) # => True print(False or False) # => False Pythonコード例 ※ 他にも否定論理積(NAND)や排他的論理和(XOR)などがある
7. 7 37 ビット演算 ビットが並んだもの ビット列とは 10110110 ビット演算とは ビット列の1を真、0を偽とした論理演算 同じ桁のビットに同時に演算する 64ビットなら64個同時に演算できる 究極の並列計算 二種類(0か1)の値を取るもの ビットとは
8. 8 37 ビット演算 否定 (NOT) 各ビットをひっくり返す(ビット反転) not 10110110 01001001
9. 9 37 ビット演算 論理積 (AND) 二つのビット列の共通部分を抜き出す 01100101 and 10110110 = 00100100 二つのビット列の同じ桁にあるビットが両方とも1なら1、それ以外は0
10. 10 37 ビット演算 論理和 (OR) 二つのビット列のどちらにもない場所を探す 01100101 or 10110110 = 11110111 二つのビット列の同じ桁にあるビットが両方とも0なら0、それ以外は1
11. 11 37 イラストロジックとビット演算 イラストロジック 数字をヒントに、マスを塗っていくパズル イラストが浮かび上がることが多い 「お絵描きロジック」「ピクロス」とも 2,2 4 2 4 2,2 1 1 2 2 3 3 2 2 1 1
12. 12 37 イラストロジックとビット演算 数字は「連続して塗るマス」を表す ルール1 4 以下の三通りの可能性がある
13. 13 37 イラストロジックとビット演算 複数の数字がある場合、「塗るマス」に ひとマス以上空白を空ける ルール2 2,2 以下の三通りの可能性がある 2マス空いてもOK 1マスは空ける
14. 14 37 イラストロジックとビット演算 4 以下の三通りの可能性がある 全ての可能性を試してみて、どの場合でも塗るマスは確定 この2マスは確定
15. 15 37 イラストロジックとビット演算 111100 and 011110 and 001111 = 001100 塗るマスを1、塗らないマスを0とする 可能性を全て列挙し、論理積(AND)を取る 確定するマスの場所が高速に求められる
16. 16 37 イラストロジックとビット演算 2,2 4 2 4 2,2 1 1 2 2 3 3 2 2 1 1 横で確定マスを探したら、次は縦の探索をする 横の探索で確定したマス 次はここに着目 この辺にも確定マスはあるが 説明の都合で未確定とする
17. 17 37 イラストロジックとビット演算 確定マス 2,2 2,2 2,2 以下の可能性のうち、上記と無矛盾なものを探したい
18. 18 37 イラストロジックとビット演算 確定 マス 100000 2,2 and 110110 100000 ANDをとったら確定マスと一致→無矛盾 A and B == A 自分と相手の論理積をとったものが自分と一致 →自分が完全に相手に含まれる 共通 部分
19. 19 37 イラストロジックとビット演算 確定 マス 100000 2,2 and 011011 000000 ANDをとって確定マスと一致しない→矛盾 A and B is not A 自分と相手の論理積をとったものが自分と一致しない →自分が完全に相手に含まれていない 共通 部分
20. 20 37 イラストロジックとビット演算 確定 マス 110110 and 110011 = 110010 確定マスと矛盾しない配置のみ列挙してANDをとる 新たな確定マスを得る
21. 21 37 イラストロジックとビット演算 2,2 4 2 4 2,2 1 1 2 2 3 3 2 2 1 1 同様な処理を縦・横を切り替えながら実行すると、(多分)絵が完成 ※ 空白確定マスの処理をやったかどうか記憶が曖昧・・・
22. 22 37 数独 行、列、ボックスに1から9の数字が1つ ずつしか入らない 図の赤いところには1は入らない それぞれの数字について、どのマスに入る可能性があるかビットマスクを作成 g1 = 000000000000100111000000111010000001010000011000000000000000000011000110000000111 g2 = 000000000000100111000010111100110001100110011000100101000000111000000000000000000 g3 = 001000010011000010000000000000000000110011000001001000101010000000000000100011000 g4 = 000110010000000000000011111000000000000111011000101101000110111000110110000000000 g5 = 000110000010101101100011101000000000000000000000101000100110101110110100100111101 g6 = 000000000001000111101000111000110001000110011000000000101110111101110110100110111 g7 = 000000000011101000101011000110111000110111000000000000101110001111110000100111001 g8 = 000000010000000000000000000000101000000000000000000000001100011001100010000101011 g9 = 000000000001101000101011000100111000100111010001101100000000000000110110000111110
23. 23 37 数独 9本のビットマスクを縦に見て、一つしかビットが立っていなければ、 そのマスに入る数字はそれしかない→数字が確定 g1 = 000000000000 g2 = 000000000000 g3 = 001000010011 g4 = 000110010000 g5 = 000110000010 g6 = 000000000001 g7 = 000000000011 g8 = 000000010000 g9 = 000000000001 マスの位置(本当は81ビット) 数字の1が、どのマスに 入る可能性があるか 9本のビットマスクについて、同じ桁に1つしかビットが立っていない 時に1となるようなビット演算を作りたい
24. 24 37 気合で作った g1 = 000000000000 g2 = 000000000000 g3 = 001000010011 g4 = 000110010000 g5 = 000110000010 g6 = 000000000001 g7 = 000000000011 g8 = 000000010000 g9 = 000000000001 b = 001000000000 考案したビット演算 9本のうち、同じ桁に1つしか立っていないビットを検出 (複数存在しても検出可能) マスの位置(本当は81ビット) このマスは3で確定 数字が確定したマスの位置
25. 25 37 Percolation 碁盤の目状の道がところどころ確率pで通行止めになっている 無事な道だけを通って左から右に通過できるか？
26. 26 37 Percolation お互いにつながっている領域を色分けする pが大きいほど、同じ色の領域(クラスター)ができる この系をパーコレーション (Percolation)と呼ぶ
27. 27 37 Percolation p 通行不能 通行可能 ある確率(0.5)を境に「ほぼ通行不能」か ら「ほぼ通行可能」に急激に変化する 振る舞いが急激に変わることを相転移 相転移する確率pを臨界点と呼ぶ
28. 28 37 Directed Percolation active inactive active inactive 時間 向き(Direction)のあるパーコレーション(Percolation) 各ボンドは確率pでアクティブ アクティブなサイトとアクティブなボンドで 下方向につながるサイトはアクティブ サイト ボンド
29. 29 37 Directed Percolation 最初に「種」を置いておく p が小さい と絶滅 p が大きい と人口爆発 https://www.s.u-tokyo.ac.jp/ja/press/2016/4602/ 相転移 乱流遷移の普遍性と関係 [M. Sano and K. Tamai, Nat. Phys. 12, 249 (2016)] ←「乱流屏風」と呼ばれる実験装置
30. 30 37 マルチスピンコーディング 0 1 1 0 1 0 1 1 ・ メモリを効率的に利用できる ・ プログラムが高速化される (かもしれない) アクティブなサイトを1、そうでないサイトを0とする マルチスピンコーディングにより・・・ マルチスピンコーディングとは二種類の値を取る自由度を ビットでまとめて表現すること
31. 31 37 マルチスピンコーディング 時刻 t 時刻 t+1 時刻tの状態から、時刻t+1のサイトの状態を決めたい まずボンドを確率pでアクティブにする アクティブなサイトとアクティブなボンドでつながればアクティブ 時刻 t 時刻 t+1 この作業をビット演算でやりたい
32. 32 37 マルチスピンコーディング 1. 現在のサイト情報をコピーする 2. アクティブなサイトを1-pの確率で殺す 3. ビットシフトして論理和(OR) shift = ※どちらかとつながればアクティブになるから
33. 33 37 マルチスピンコーディング アクティブなサイトを1-pの確率で殺すには 01101011 01110010 = 01100010 and 01110010 1. 各ビットがランダムに確率pで1となるビット列を作る 2. サイト状態と論理積(AND)を取る 3. 確率pで生き残る(確率1-pで死ぬ)
34. 34 37 ランダムビット列 01110010 各ビットがランダムに確率pで1となるビット列を作る 各ビットが独立に確率pで1、1-pで0となるような ランダムビット列を高速に作るアルゴリズムが必要 →作った 普通に作るとNビットのビット列にN回の乱数が必要 →ビットレベルの並列性が活かせない arXiv:1808.05009 HW, S. Morita, S. Todo, N. Kawashima, J. Phys. Soc. Jpn. 88, 024004 (2019)
35. 35 37 結果１：ランダムビット列生成速度 普通に実装すると、スカラー実装の方が早い 有限桁法で0.625から補正すると、PO法＋補正が効率的 スカラー実装 BS法 PO法 BS法+補正 PO法+補正 Larger is better p = 0.6447 (DPの臨界点) Millions of bits per second (メガビット生成毎秒)
36. 36 37 結果２：Directed-Percolationへの応用 64ビットマルチスピンコーディングにより14倍の高速化 実行時間 Lower is better
37. 37 37 まとめ • ビット演算は究極の並列化であり、ハマる と極めて高速 • スピンを複数まとめるテクニックをマルチ スピンコーディングと呼ぶ • 計算機に近い技術が物理の論文になること がある
38. 38 37 以下補足資料 各ビットが独立に確率pで1、1-pで0となるような ランダムビット列を高速に作るアルゴリズム • Binomial-Shuffle 法 • Poisson-OR 法 • 有限桁法と上記のハイブリッドアルゴリズム https://qiita.com/kaityo256/items/99efbe7ae9786d0f4351 解説記事 H. Watanabe, S. Morita, S. Todo, and N. Kawashima, J. Phys. Soc. Jpn. 88, 024004 (2019) 論文 公開ライブラリ https://github.com/kaityo256/rbs
39. 39 37 Binomial-Shuffle (BS)法 まず「ビットが何個立つか」を計算し、 次に場所をランダムにシャッフルする 11100000 01100010 位置のシャッフルにRobert-Floydのサンプリング法を使う NビットあるとN回の乱数が必要 →ビットが立たない場所に乱数を振るのは無駄 →ビットが立つところだけに乱数を使いたい
40. 40 37 Robert-Floyd's sampling algorithm N個の中からM個をランダムに選ぶアルゴリズム 乱数はM回しか振らなくて良い 1. J ← N-M+1 2. J個のなかからランダムに選ぶ 1. もし選ばれてないものを選んだら、そのまま選ぶ 2. もし選ばれていたらJ+1個を選ぶ 3. J ← J+1 4. J<Nなら 2.へ戻る N=8, M=3の例
41. 41 37 Robert-Floyd's sampling algorithm 例えば4つの中から2個ランダムに選びたい 1. 最初は3つの中からランダムに一つ選ぶ 2. 次に4つの中からランダムに一つ選ぶ 既に選んだのを選んだ そのまま選ぶ 選んでないのを選んだ 4つ目を選ぶ
42. 42 37 Robert-Floyd's sampling algorithm 一度目に選ばれる 二度目に選ばれる 直接選ばれる 既に選んだものが選ばれる 必要な乱数は選ぶ数(二回)だけ
43. 43 37 Binomial-Shuffle (BS)法 立つビット数の計算に乱数を一回使う ビット数は二項分布 (Binomial-Distribution)に従う 平均乱数生成回数 1 + 𝑝𝑁 ビット位置のシャッフル(Shuffle)に、ビット数 (平均pN)回の乱数を使う 確率pの試行をN回で何回成功するか？
44. 44 37 Poisson-OR (PO) 法 1. 適切なパラメタλに従うポアソン分布でkを生成する 2. 1ビットだけランダムに立つビット列をk個用意する 3. それらすべての論理和(OR)を取る 01000000 00000010 00010000 01000000 01010010 or = k 確率pでビットが立つビット列完成 S. Todo and H. Suwa, J. Phys.: Conf. Ser. 473, 012013(2013)
45. 45 37 Poisson-OR (PO) 法 1ビットだけ立ったビット列の数を作るのに乱数一回 この数はポアソン分布(Poisson-distribution)に従う 1ビットだけ立ったビット列をk個作るのに乱数k回 kの期待値は N log(1-p) 最後に全てのビット列の論理和(OR)を取る 平均乱数生成回数 1 + 𝑁 log 1 − 𝑝
46. 46 37 有限桁法 p = 0.5に近い時は？ 有限桁法 「pが大きい時」は、1-pで作ってビット反転 BS法、PO法は「pが小さい時」に有利 BS法 PO法 p 乱 数 生 成 回 数
47. 47 37 有限桁法 良い乱数 = 各ビットが確率1/2で独立に1になっている 01010101001001110001000010101111 01001010011001111111100000111000 00011000001010011000001000111110 10011010010101010000101000110011 00111010011101001111101100110011 メルセンヌ・ツイスタ法で作成した32ビット乱数列 つまり、 p= 0.5なら乱数一回で作ることができる
48. 48 37 有限桁法 確率1/2でビットが立っているビット列 x1, x2 01010101 10011001 x1 x2 01010101 10011001 00010001 x1 and x2 and = 01010101 10011001 11011101 x1 or x2 or = 確率1/4のビット列 確率3/4のビット列 1/4 = (0.01)B 3/4 = (0.11)B
49. 49 37 有限桁法 1/2 = (0.1)B 1/4 = (0.01)B 3/4 = (0.11)B 5/8 = (0.101)B n個の乱数で二進数表記n桁の確率を表現できる x1 x2 AND x1 x2 OR x1 x3 OR (x2 AND x1) 論理式の作り方： pを二進数表記して、右から「1ならAND」「0ならOR」 (0.0101)B = 5/16 3 2 1 x4 AND (x3 OR (x2 AND x1))
50. 50 37 ハイブリッド法 p = 0.51のビット列が欲しい時 1. 有限桁法で p = 0.5のビット列を作る 2. BS法かPO法でp=0.02のビット列を作る 3. 二つのビット列のORを取る 1 - p =(1-0.5)(1-0.02) ORは「どちらも0なら0」 できたビット列の0の確率 二つとも0の確率 p = 0.51
51. 51 37 ハイブリッド法 有限桁法の精度を上げるほど ・ 近似ビット列の生成に必要な乱数生成回数は増える ・ 補正に必要な乱数生成回数は減る 確率pに依存して最適な組み合わせが存在する p=0.6447の場合 p=1/2 (0.5) から p = 0.2894で補正 p=5/8 (0.625) から p = 0.0197で補正 有限桁法で作る BS法/PO法で作る
52. 52 37 ハイブリッド法の地図 平 均 乱 数 生 成 回 数 p = 1/4 からの補正 p = 3/8 からの補正 32ビットなら高々7回の乱数生成で 任意の確率のビット列を生成可能 欲しい確率p