Quartz 5

Hecatia

Properties1
tagslab

10 min read

Hecatia

Thesis で作っているHEコンパイラ

Hecatia: Homomorphic Encryption Compiler for Auto-vectorizaTIon using equAlity-saturation

Architecture

2022-10-27

Rustを用い, cargo workspace として複数の crate(パッケージのこと)に分けている

  • homc: CLI
  • homir: HomIR
  • homir-codegen-lattigo: HomIR -> Lattigo
  • homir-interpreter: HomIR のインタプリタ
  • homir-profile: HomIR 実行時のプロファイルのビジュアライザ
  • homml: HomML 定義, HomML -> HomIR へのlowering
  • homml-optimizer: Equality Saturation による式表現最適化
  • executor(Go): Lattigo 実行用
  • homml-kernels: HomML で書かれたHEアプリケーション

コンパイラ

書き換え規則

  • 準同型演算に関するもの

    • 可換性
      • hom-add-comm: (+ ?a ?b) => (+ ?b ?a)
      • hom-sub-comm: (- ?a ?b) => (- ?b ?a)
      • hom-mul-comm: (* ?a ?b) => (* ?b ?a)
      • hom-add-self: (+ ?a ?a) => (* ?a (ecd (const 2)))
      • hom
    • 結合性
      • hom-add-assoc: (+ ?a (+ ?b ?c)) <=> (+ (+ ?a ?b) ?c)
    • 分配律
      • hom-add-dist: (+ (* ?a ?c) (* ?b ?c)) => (* (+ ?a ?b) ?c)
    • 0元
      • hom-mul-0
      • hom-rot-0
    • 単位元
      • hom-mul-1

  • 2022-10-27 #49

  • simd_index_op

(vec (# ?a 1) (?a 3) (?a 2) (?a 4))
=> (simd-index-op)
(lintrans ?a (vec 1 3 2 4))
  • simd_bin_op
(vec (+ ?a1 ?b1) (+ ?a2 ?a2) ...)
=> (simd-bin-op)
(+. (vec ?a1 ?a2 ...) (vec ?b1 ?b2 ...))

  • ループに関するもの

  • egg, CSE はしてくれるのか? -> No

    • (+ (+ (* x 3) x) (* x 3)) => (let _1 (* x 3)); (+ (+ _1 x) _1)

  • rep .+ を + を変換するrule ✅ 2024-07-17

  • 行列積しかしない計算グラフならパッキングの段階で予め転置した状態で入れたい

    • やはり最適なデータ配置も考える?

  • Hecatia CostFunction

2022-04-19

2022-05-12

2022-10-26

  • blur filterの最適化もしよう ✅ 2024-07-17

  • 各IR毎に実行時間取れるように ✅ 2024-07-17

  • profile コマンド, 個で比較できるように ✅ 2024-07-17

    • 変えて和積の計測とかしたいので

  • optimizeにかかった時間表示

  • egg v0.9 に上げよう

  • solverを使うoption

  • explanationでは CSE やるが, lowering の時にしてくれないので、自前で実装する必要がある ✅ 2024-07-17

    • criticalな部分ではないが実装する必要あり

2022-10-27

2022-07-20

  • 色々issues潰した

2022-07-23

  • rescale opで扱えるように ✅ 2024-07-17
  • bootstrap bs: id みたいに明示的に呼べるように ✅ 2024-07-17
  • op毎のlevel, 精度, 時間とかprofiling出来るように
  • if/else support ✅ 2024-07-17
  • interactive support ✅ 2024-07-17

2022-07-24

2022-07-25

  • matmul 動くまでバグ取り

2022-08-19

  • バグ修正

2022-09-16

2022-09-17

  • インデックスアクセス構文の導入
  • スライド by 2022-09-21
    2022-05-16
  • parser
  • plain-executor
  • optimizer connector
    作っていた

2022-05-20

  • lowering 完成
    • set_index 動くように

2022-05-25

2022-08-30

2022-10-17

  • Microsoft SEAL
    • について計算順序の違いで誤差とか変わるか検証

実験 HEカーネルに対するコンパイル時最適化時間

    \begin{table}
        \centering
        \caption{HEカーネルに対する最適化時間}
        \begin{tabular}{llll}
            \toprule
            {}         & baseline(ms) & 等式飽和(ms) & ソルバ(ms) \\
            kernel     &              &          &         \\
            \midrule
            内積($n=4$)  & 0.1242       & 51.9     & 42.69   \\
            行列積($d=2$) & 0.4154       & 79.53    & -       \\
            行列積($d=3$) & -            & 125.7    & 151.4   \\
            \bottomrule
        \end{tabular}
    \end{table}

実験: 生成されたHEカーネルに対する実行時間

    \begin{table}
        \centering
        \caption{生成されたHEカーネルに対する実行時間}
        \begin{tabular}{llll}
            \toprule
            {}         & baseline(ms) & 等式飽和(ms) & ソルバ(ms) \\
            kernel     &              &          &         \\
            \midrule
            内積($n=4$)  & -            & -        & -       \\
            行列積($d=2$) & -            & -        & -       \\
            行列積($d=3$) & -            & -        & -       \\
            \bottomrule
        \end{tabular}
    \end{table}

2022-11-06

  • flatten_then 修正
  • homc optimize -> lowering -> codegen コマンドを分離
  • lowering のバグ修正, golangで未使用な変数が生成されないように
  • op-get-exchange 規則を追加し, Total Sum > rewrite が出来るように

2022-11-10
todo

(let v (ecd (const 1)))
(let c (enc v)) @local

のとき, ASTは上から順に構築するので1Passでは v に @local を付けられない

  • 逆順で Ir[] iterしてpropagateさせた

  • mult_depth も全体だけで良いのでIR列に対して計算できれば良い

    • profileで途中のscale, level追いたくなったら後から Ir[] にコメント挿入すれば良い

  • #, #= はmacro

2022-11-13

  • CBC solverで解く時にどういう定式化をしているか ✅ 2024-07-17

2022-11-26

(let i 0 (let j 1 (then
    (let k 0 (+. i k)) => (+. i 0)
    (let k 1 (+. i k)) => (+. i 1)
)))

when it has no changes before and after let-expand in data. E-Graph is regarded as saturated.

2022-12-07
これ治ったと思ったが治っていない? todo

  • 2022-09-21-zemi

  • 行列積 HE kernel について で

    • naive
    • simd化された

  • で最適化時間, 速度, 命令数, ノイズ推移比較

  • lattigo の線形変換を調査する

  • スカラ演算をvectorizeする simd ruleをexample実装する

    • `(vec (#. ? ?) (#. ? ?) …) -> (# (vec ? ? …) (vec ? ? …))

  • lintrans 演算を実装する

2022-09-16

  • 順不同で (get a i) をまとめられるようにする
    • まずはランダムな順番の (get a i) を (lintrans a (vec i i i i)) に出来るように
    • 行, 列, diagな (get) をまとめられるように ✅ 2024-07-17
  • ループ展開をしたものに対して上手く (lintrans) に出来るかどうか ✅ 2024-07-17
  • profileモードで出力したJSONを react-flow で可視化 ✅ 2024-07-17
    • 各depthでのノイズ量とかみたい ✅ 2024-07-17
  • HE Girl 「可換性, 結合性を書き換え規則に含めると状態数が爆発するので注意 [1]」

2022-11-01

  • 線形変換による方法とSIMD化されたものの比較 ✅ 2024-07-17
    • compileするときにoptエラー
      • mlの要素 ex. (vec 4 5 6 7) => (vec 6 6 6 7) 自体が書き換わっているので merge あたりか?
    • flatten_then を作る 2.5h
    • 線形変換自体を最適化する ✅ 2024-07-17
  • IRの mult-depth バグ修正 3.5h

2022-12-09

  • 愚直にshift networkを作ってそれを最適化(=回転量最小化)するでも良さそう

2022-05-27-

Secure Outsourced Matrix Computation and Application to Neural Networks > 2 3 Linear Transfomations

2023-01-11

  • profileにtimeを追加してop毎に時間出せるようにする
  • lintrans-matmulとcompiler-optimized-matmulの比較をする

2023-01-20

indexingから線形変換為の定数行列を作成するコードwip

  • ループ展開せずに rep に対し直接変換出来たら良いと思って
  • rep のループ定数の直積 ex. i => 0..2, j in 0..2 => (i, j) = [(0, 0), (0, 1), (1, 0), (1, 1)] から直積を作成しループ変数を使う式 ex. i + j = [0, 1, 1, 2] を評価して定数化する
    • -> 辛いので, indexing列から定数行列作る

Graph View

Backlinks