Quartz 5

Total Sum

Properties1
tagsfhe/algorithm

4 min read

algorithm

  • 総和:
  • どちらも, repeated doublingで depth add, rots

rewrite

  • total-sum-folding
(rep + i 4 (# a i))
=> (total-sum-folding)
(let _1 (+ a (L a 2)))
(let _2 (+ _1 (L _1 1)))
_2

ex. 内積

(let a (enc (ecd (input 4))))
(let b (enc (ecd (input 4))))
(rep + i 4 (+ (# a i) (# b i)))
=> (total-sum-folding)
(let _1 (+ a (L a 2)))
(let _2 (+ _1 (L _1 1)))
_2
  • こういうときどうするのか

e.g. 要素和

for i in 0..10:
	z[i] = x[i] + y[i]

を考えると,

  • スカラーの演算なので x[i] を x[0] に持ってきて足すみたいなことをする(naive get_index)

    • 各反復で異なる量の回転をする
      • 異なる演算なので一つのSIMD演算にまとめる方法はない

  • HECOではSIMD演算を回転せずに行う

    • 足した後に回転する

  • 各反復で回転せずに足すので同じ演算である加算をしている

    • CSE すれば単一のSIMD演算になる

  • まだ, 足した後の回転は残っている

Link to original

expand-get-index: (# ?a ?k) => (L (* ?a (ecd (mask (set ?k)))) ?k) して

(let z
  (rep + i 3
    (#= z i (*
      (# x i)
        => (expand-get-index)
        (L (* x (ecd (mask (set i)))) i)
      (# y i)
        => (expand-get-index)
        (L (* y (ecd (mask (set i)))) i)
    ))
  )
)
  • hom-rot-mul-exchange: (* (L ?a ?k) (L ?b ?k)) => (L (* ?a ?b) ?k)
  • hom-mul-dist: (* (* ?a ?c) (* ?b ?c)) => (* (*?a ?b) (* ?c ?c))
    • [1,2,3,4] * [0,1,1,1] * [5,6,7,8] * [0,1,1,1] = [5,12,21,32] * [0,1,1,1]
(rep i 3
  (let m (ecd (mask (set i))))
  (let v
    (* (L (* x m) i) (L (* y m) i))
      => (hom-rot-mul-exchange)
      (L (* (* x m) (* y m)) i)
      => (hom-mul-dist)
      (L (* (* x y) m))
  )
  (#= z i v)
)
  • expand-set-index: (#= ?a ?k ?v) => (= ?a (+ (* ?a (ecd (mask (setinv (set ?k))))) (* (L ?v (-. 0 ?k)) (ecd (mask (set ?k))))))
    • (#= [1 2 3 4] 1 [5 0 0 0]) = [1 2 3 4] * [1 0 1 1] + [5 0 0 0] << -1 * [0 1 0 0]
; ex. x = [1 2 3], y = [4 5 6], i = 1
(rep + i 3
  (let m (ecd (mask (set i)))) ; [0 1 0]
  (let v (L (* (* x y) m)))) ; [10 0 0]
  (#= z i v)
    => (expand-set-index)
    (let im (ecd (setinv (mask (set i)))))
    (= z (+
      (* z im) ; 
      (* (L v -i) i)
    ))
)

  • rep-assign-rep-op

    • どうにか副作用の無い形に出来ないか?
      • unroll?

  • expr-expand

(let z 0) ; z = 0
(rep i 2
  (= z (+ z i)) 
)
  => (rep-unroll)
  (let i 0) ; i = 0
  (= z (+ z i))
    => (expr-expand)
    (= z (+ 0 0)) ; z => 0, i => 0, z = (+ 0 0)
  (let i 1) ; i = 1
  (= z (+ z i)) ; z => (+ 0 0), i => 1, z = (+ (+ 0 0) 1)
    => (expr-expand)
    (= z (+ (+ 0 0) 1)
(rep + i 4
  (# a 0)
)
=> loop-unroll
(+
  (then (let i 0) (# a 0))
  (+ 
    (then (let i 1) (# a 0))
    (+
      (then (let i 2) (# a 0))
      (then (let i 3) (# a 0))
    )
  )
)
=>
()

CPUのSIMD op

Fold loopまたはReduce loopは，1つまたは複数の配列から要素を順次読み込み、それらをアキュムレータで結合する算術演算を行います．計算の最後には1つの値が得られます。ただしmap loopとは異なり、この手の算術演算には結合性と可換性が必要です。浮動小数点演算は、丸めの関係で結合性がないため、整数に対するfold loopのSIMDコードしか生成できません。

  • 関係ない

  • 2022-08-30 loop-folding は本質的には関数結果のメモ化に等しいと思う, CSE みたいな

    • ので優先度は低め
    • 再帰で表すことが出来れば 式 の同じ引数に対する let 導入で表せる?

  • HECO がやっていることを 式 のメモ化で説明もしたいし時間あるか?

Graph View

Backlinks