homml-optimizer SIMD

Thesis の新規性の部分

やりたいこと

• 行列積のような多重ループと配列アクセスを伴うプログラムをHE-SIMD化したい

どうやって?

1. naiveな3重ループのmatmul $\mathrm{Naive}$を用意する
2. 多重ループをループ展開
3. Equality Saturation により簡約し, get-index, set-indexのプログラム $\mathrm{Opt}$ にする
4. プログラムを走査し, shift network を作成 ✅ 2024-07-17
5. shift-columnを 線形変換 で表し, プログラム $\mathrm{Simd}$ を得る ✅ 2024-07-17
6. 線形変換 を最適なshiftで表す ✅ 2024-07-17

• 2022-04-15 Q: 回転演算も置換では?

• 2022-05-23 Q: 行列積を表す写像から線形変換を用いたアルゴリズムへの変換は本当にコスト最小の変換なのか?

• 選択多項式

• 関数型言語の最適化の話は車輪の再発明になってしまうのでHEコンパイラ特有の仕事に集中する

  • インデックスアクセスを伴うプログラムのvectorize
  • 乗算深さ最適化
  • HE特有の制御(ReScale のタイミング)

• 線形変換によるHE行列積

• 行列積から線形変換による方法への書き換え

• Q: 線形変換相当の操作がshift columnsでも行えるのでその方が早い?

  • -> 同じ位だった
    

• 密なlintransの時はあまり速度変わらないのか

• 暗号文の並び替えにも複数のやりかたがあり, 愚直な線形変換より早い方法が存在するはず hypo

  • shift network

indexingからの変換

2023-01-16

(let c (enc (ecd (const 0)))
(#= c 0 (+ (* (# a 0) (# b 0)) (* (# a 1) (# b 2))))
(#= c 1 (+ (* (# a 0) (# b 1)) (* (# a 1) (# b 3))))
(#= c 2 (+ (* (# a 2) (# b 0)) (* (# a 3) (# b 2))))
(#= c 3 (+ (* (# a 2) (# b 1)) (* (# a 3) (# b 3))))
)
; ops (mult, cmult, rot)
; #=: (0, 2, 1)
; #: (0, 1, 1)
; assign: 1 #=, 2d #, d mult
;       = (0, 2, 1) + (0, 2d, 2d) + (d, 0, 0)
;       = (d, 2d + 2, 2d + 1)
; total: d^3 assign = (d^3 d, d^3(2d + 2), d^3(2d + 1))

• 展開された形だとslots数に対して爆発する?

(rep then i $DIM
  (rep then j $DIM
    (rep then k $DIM
      (let ai (# a (+. (*. i $DIM) k))
      (let bj (# b (+. (*. $DIM k) j))
      (let u (+. (*. i $DIM) j)
      (#= c u (+ (# c u) (* ai bj)))
      )))
    )
  )
)

• ループ変数は特別な LoopValue にして評価も幅を持たせる?
  • LoopValue に対する部分評価は幅を持たせる
    • ex. i = 0..2, j = 0..2, (*. i j) = (
  • やっていることループ解析では -> まぁそう

(let ai (# a (+. (*. i $DIM) k))
(let bj (# b (+. (*. $DIM k) j))
(let u (+. (*. i $DIM) j)
(#= c u (+ (# c u) (* ai bj)))
)))
 

を

(let a (enc (ecd (vec 1 2 3 4)))
(let b (enc (ecd (vec 5 6 7 8)))
(let c
(+ (L (* (+ (* (# a 0) (# b 0)) (* (# a 1) (# b 2)))
    (ecd (mask (set 0)))) 0)
(+ (L (* (+ (* (# a 0) (# b 1)) (* (# a 1) (# b 3)))
    (ecd (mask (set 1)))) (-. 0 1))
(+ (L (* (+ (* (# a 2) (# b 0)) (* (# a 3) (# b 2)))
    (ecd (mask (set 2)))) (-. 0 2))
   (L (* (+ (* (# a 2) (# b 1)) (* (# a 3) (# b 3)))
    (ecd (mask (set 3)))) (-. 0 3))
)))
c)
))
; ops (mult, cmult, rot)
; elm: 2 d^3 #, d mult, 1 cmult, 1 rot = (d, d + 1, d + 1)
; total: d^2 elm = (d^3, d^2(d + 1), d^2(d + 1))

にして(accumrating),

(+
    (* (lintrans a (vec 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0))
       (lintrans b (vec 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0)))
    (* (lintrans a (vec 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1))
       (lintrans b (vec 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1))
))
; ops (mult, cmult, rot)
; lintrans: (1, d, d)
; total: 2d lintrans = (2d, d^3, d^3)

にしたい(batching).

• (#= c r ... (# a l)) は l -> r への移動なので $M_{r,l}$ だけ 1 の置換行列を作成

  • (# a l) make時には $r$ が不明なのでincrementalに行列を作成したい
  • rep 来たらループ変数に依存する変数をindexingに使っていたら置換行列作る?

• ex. c[0] = a[0 -> ?] * b[0 -> ?] + a[1 -> ?] * b[2 -> ?]

  • c[0] 走査時に ? = 0 が決定する
  • a[i -> j] は $1_{j,i}$ を作成する
  • c[0, 1, 2, 3] = a[0 -> 0, 0 -> 1, 2 -> 2, 2 -> 3] * b[0, 1, 0, 1] + a[1, 1, 3, 3] *b[2, 3, 2, 3]
    • に対して, 第1項は $1_{0,0}+1_{1,0}+1_{2,2}+1_{3,2}=1_{\{(0,0),(1,0),(2,2),(3,2)\}}$ というように足し合わせることができる