格子暗号＋ハードウェア最前線：　Intel HEXL (インテル開発の独自ハードウェア）による高速化の検証

## 概要

最近のいくつかの記事で、OpenFHEを用いて、CKKS形式の

- ブートストラップと演算の組み合わせ
- 非線形演算チェビシェフ近似
- プロキシ再暗号化
- Threshold 暗号構成
- 線形回帰モデルの学習チュートリアル

などを行ってきました。

今までのチュートリアルでは、ソフトウェアはあくまでも普通のコンピュータインストラクションを用いて実行されていました。

今回は、OpenFHEがサポートしている、

**Intel Homomorphic Encryption Acceleration Library (Intel HEXL)**

を用いてビルドを行い、
ハードウェアによってどのくらいの高速化が実現可能なのか、という検証をしてみます。

また、検証を行う上で、スレッディングのON/OFFも切り替えて、
シングルコア構成でも速度評価を行ってみたいと思ったため、そちらも試してみます。


## Itenl Hexl とは

## ビルド手順

まず、`openfhe-development/third-party` に

https://github.com/openfheorg/openfhe-hexl

このレポジトリをクローンし、`hexl` を個別にビルドします。
その後は、`openfhe-development`のチュートリアルを行った時のフラッグとして、

`-DWITH_INTEL_HEXL=ON -DINTEL_HEXL_PREBUILT=ON`
のフラッグによりHEXLのON/OFFを切り替えることができます。


わたしが実際に使ったフラッグ（MacOS＋Intelの場合）はこちらです。

```
-DWITH_INTEL_HEXL=ON -DINTEL_HEXL_PREBUILT=ON -DWITH_NATIVEOPT=ON -DCMAKE_CROSSCOMPILING=1 -DRUN_HAVE_STD_REGEX=0 -DRUN_HAVE_POSIX_REGEX=0 -DWITH_OPENMP=ON
```

`openfhe-configurator`の中で、

```
scripts/build-openfhe-development-hexl.sh
```
を使うことで`Hexl`と共にビルドを実行することができます。

うまくいけば、

```bash
-- Apple Intel detected
-- OPENMP_LIBRARIES: /usr/local/opt/libomp/lib
-- OPENMP_INCLUDES: /usr/local/opt/libomp/include
-- OpenMP_CXX_FLAGS: -Xpreprocessor -fopenmp -lomp -Wno-unused-command-line-argument
-- OpenMP_CXX_LIB_NAMES: libomp
-- Found OpenMP_C: -Xpreprocessor -fopenmp -lomp -Wno-unused-command-line-argument
-- Found OpenMP_CXX: -Xpreprocessor -fopenmp -lomp -Wno-unused-command-line-argument
-- Found OpenMP: TRUE

-- Intel HEXL found
-- INTEL_HEXL_INCLUDE_DIR: /usr/local/include
-- INTEL_HEXL_LOCATION: /usr/local/lib/libhexl.1.2.4.dylib

```

のようなログがCMakeの時に出力され、

```
Building openfhe-development with cc  cxx  cmake flags -DWITH_INTEL_HEXL=ON -DINTEL_HEXL_PREBUILT=ON -DWITH_NATIVEOPT=ON -DCMAKE_CROSSCOMPILING=1 -DRUN_HAVE_STD_REGEX=0 -DRUN_HAVE_POSIX_REGEX=0 -DWITH_OPENMP=OFF succeeded.
```

ビルド終了時にこのようなログが表示されるはずです。


## 検証に使うプログラム

https://github.com/kenmaro3/openfhe-tutorial/blob/main/mytest_eval_many_bs.cpp

こちらのプログラムを検証用に使います。
やっていることは、CKKS形式のブートストラップを、テスト用パラメータのもとで１０回繰り返し、
全体の時間を測っているだけの単純なプログラムです。


## 検証内容

- **OpenMPを用いたスレッディングのON/OFF**
- **Intel Hexl を用いたハードウェア高速化のON/OFF**

を切り替えつつ、スレッディングとハードウェア高速化の、
実オペレーションへの寄与について考察してみます。


## 検証環境①

まず自分が持っている環境で試すことにしました。

```
Processor: 2.3 GHz 8-Core Intel Core i9
Memory: 64 GB 2667 MHz DDR4
```

です。

ここで、Intel HEXLは AVX512 を用いて多項式演算を高速化しているということでしたが、
わたしの実行環境では、

```bash
sysctl -a | grep avx2

hw.optional.avx2_0: 1
```

```bash
sysctl -a | grep 512

kern.wq_max_threads: 512
net.inet.ip.dummynet.red_avg_pkt_size: 512
net.inet.ip.mcast.maxgrpsrc: 512
net.inet.tcp.mssdflt: 512
net.inet.tcp.rcvsspktcnt: 512
net.link.fake.buflet_size: 512
net.inet6.ip6.mcast.maxgrpsrc: 512
net.utun.max_pending_input: 512
net.ipsec.max_pending_input: 512
hw.optional.avx512f: 0
hw.optional.avx512cd: 0
hw.optional.avx512dq: 0
hw.optional.avx512bw: 0
hw.optional.avx512vl: 0
hw.optional.avx512ifma: 0
hw.optional.avx512vbmi: 0
```

```bash
/usr/sbin/sysctl -n machdep.cpu.features machdep.cpu.leaf7_features

FPU VME DE PSE TSC MSR PAE MCE CX8 APIC SEP MTRR PGE MCA CMOV PAT PSE36 CLFSH DS ACPI MMX FXSR SSE SSE2 SS HTT TM PBE SSE3 PCLMULQDQ DTES64 MON DSCPL VMX SMX EST TM2 SSSE3 FMA CX16 TPR PDCM SSE4.1 SSE4.2 x2APIC MOVBE POPCNT AES PCID XSAVE OSXSAVE SEGLIM64 TSCTMR AVX1.0 RDRAND F16C
RDWRFSGS TSC_THREAD_OFFSET SGX BMI1 AVX2 SMEP BMI2 ERMS INVPCID FPU_CSDS MPX RDSEED ADX SMAP CLFSOPT IPT SGXLC MDCLEAR IBRS STIBP L1DF ACAPMSR SSBD
```

となっており、avx512ifma ないやん、、となりました。
したがって、後述の検証環境②で、AVX-512を持っているクラウド環境で試すことにしました。

しかしながら、わたしの環境でも一定の高速化が見受けられたため、
この結果も参考として検証結果①として言及しておきます。




## 検証結果①

以下のような実行結果となりました。
全ての数値は`msec`記載となっています。


|           | OpenMP  無し | Open MP 有り | 
|-----------|--------------|--------------|
| HEXL 無し |        47197 |        22759 |  
| HEXL 有り |        36615 |        16955 |


![Screen Shot 2022-12-06 at 13.59.27.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/519792/d24d6abd-264c-c971-80f1-a4b5fc04994a.png)


実行時間としては、ナイーブですが、

- **HEXLにより約２０％の改善**
- **OpenMP により（１６スレッドの下で）約５０％の改善**

となりました。



## 検証環境②

https://learn.microsoft.com/en-us/azure/virtual-machines/sizes-compute

ここでも言及されている、
`Fsv2-series`の　Azure instance の

![Screen Shot 2022-12-06 at 15.32.59.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/519792/e9b18ca1-18dc-4687-b64c-cd9a17490db4.png)

`Standard_F8s_v2` を使用しました。


## 検証結果②

正直なところ、あまり結果としては自分の計算環境を使った時と変わらない
という結果になりました。
Azureマシンは８コア８スレッドで、スレッド数としてはわたしの環境の方が大きく、
HEXLの影響は大きいですが、OpenMPによるスレッディングの方が現実的には大きく作用している、
と結論づけていいように思います。


|           | OpenMP  無し | Open MP 有り |  
|-----------|--------------|--------------|
| HEXL 無し |        35561 |        17442 | 
| HEXL 有り |        27333 |        15597 | 


![Screen Shot 2022-12-06 at 16.07.18.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/519792/2ce53c52-1ec6-88ca-65da-74f51b7c0566.png)



## まとめ

今回は、OpenFHEがサポートしている、

**Intel Homomorphic Encryption Acceleration Library (Intel HEXL)**

を用いてビルドを行い、
ハードウェアによってどのくらいの高速化が実現可能なのか、という検証を実施してみました。

ナイーブな測定ではありましたが、

- **HEXLにより約２０％の改善**
- **OpenMP により（１６スレッドの下で）約５０％の改善**

という結果になりました。
実運用としては、マシンパワーを使ってもっとスレッドの数を増やし、
さらにそのマシンがHEXLを搭載していればかなりのランタイムの向上につながると考えられます。

以前の記事でご紹介した、線形回帰モデルの学習においても、
かなりナイーブな実装で約数時間〜１０時間程度の時間がかかっていましたが、
マシンパワーを用いることでそれが数十分くらいには現在のハードウェアを持ってしても短縮可能であろうと考えられるため、実用に耐えうるかなという印象です。

次回は、このIntel HEXLが一体どのようにして格子暗号のランタイム短縮を実行しているのか、
ということについて言及したいと思います。

面白くなりそうです。


今回はこの辺で。

@kenmaro