CPU/GPU高速化セミナー ~暗号アルゴリズムの高速化~(2024/05/27)

2.8K Views

June 03, 24

スライド概要

フィックスターズでは、様々なデータを対象にソフトウェア処理の実装や高速化を行っています。
その一つの高速化対象として、暗号アルゴリズムがあります。
これらの暗号化や署名生成といった処理は、ユースケースに応じて様々なアーキテクチャ上で実行されます。

本セミナーでは、暗号アルゴリズムで頻出するモンゴメリ乗算について、Intel AVX-512IFMA52 命令セットを搭載した CPU 向けの実装を解説します。

具体的には、公開済みのブログ記事の内容をより詳細に、そして開発の背景なども交えてお話します。

<出典:当社ブログ記事>
・Intel AVX-512IFMA52 命令セットによるモンゴメリ乗算の高速化 :
 https://proc-cpuinfo.fixstars.com/2024/01/intel_avx-512ifma52/


<講演内容>
・暗号アルゴリズムを実行するプラットフォームとユースケース
・モンゴメリ乗算の重要性
・Intel CPU の AVX-512 命令セットと AVX-512IFMA52 命令サブセット
・モンゴメリ乗算の SIMD 実装例
・実装例に対する性能評価


<フィックスターズのサービス内容>
・ソフトウェア高速化
 https://www.fixstars.com/ja/services/acceleration
・GPU向け高速化
 https://www.fixstars.com/ja/services/gpu
・組み込み高速化
 https://www.fixstars.com/ja/services/embedded

profile-image

フィックスターズは、コンピュータの性能を最大限に引き出すソフトウェア開発のスペシャリストです。車載、産業機器、金融、医療など、幅広い分野での開発経験があります。また、ディープラーニングや機械学習などの最先端技術にも力を入れています。 並列化や最適化技術を駆使して、マルチコアCPU、GPU、FPGA、量子アニーリングマシンなど、さまざまなハードウェアでソフトウェアを高速化するサービスを提供しています。さらに、長年の経験から培ったハードウェアの知識と最適化ノウハウを活かし、高精度で高性能なアルゴリズムの開発も行っています。       ・開催セミナー一覧:https://www.fixstars.com/ja/seminar   ・技術ブログ :https://proc-cpuinfo.fixstars.com/

シェア

またはPlayer版

埋め込む »CMSなどでJSが使えない場合

関連スライド

各ページのテキスト
1.

CPU/GPU高速化セミナー 暗号アルゴリズムの高速化 Copyright © Fixstars Group

2.

本セミナーの構成 1. 会社紹介 2. 暗号のユースケースと実装対象アーキテクチャの関係 3. Intel CPU の AVX-512 命令セットと AVX-512IFMA52 命令サブセット 4. モンゴメリ乗算の有用性 5. モンゴメリ乗算の SIMD 実装例 6. 実装例に対する性能評価 Copyright © Fixstars Group 1

3.

本セミナーの位置づけ 弊社でサービス展開している、ソフトウェアによる処理速度向上に関連した 様々な技術情報を発信しています • 性能モデルの理論と実践 (発表資料) • ソフトウェア性能の理論的根拠となる性能モデルの 使用方法と実践例 • 浮動小数点から文字列への高速変換の論文を読んでみた (発表資料) • • Ryu のアルゴリズムの解説と GPU移植 今回の内容 • 暗号アルゴリズムで頻出するモンゴメリ乗算の CPU向け高速化実装 • こんな方に向いています • 暗号処理およびその他データ処理について、性能を意識した開発 を行っている方 • 実用的なアルゴリズムの CPU 高速化事例を知りたい Copyright © Fixstars Group 2

4.

発表者紹介 冨田 明彦 毛 德君 (Dejun Mao) ソリューションカンパニー 営業企画 ソリューション第五事業部 リードエンジニア 2008年に入社。金融、医療業界において、ソ フトウェア高速化業務に携わる。その後、新規 事業企画、半導体業界の事業を担当し、現職。 2021年に新卒入社。業務では主に、暗号アルゴリ ズム、およびシステムセキュリティの分野を担当。 専門は、グラフ理論を中心としたアルゴリズム。 Copyright © Fixstars Group 3

5.

フィックスターズの ご紹介 Copyright © Fixstars Group 4

6.

フィックスターズの強み コンピュータの性能を最大限に引き出す、ソフトウェア高速化のエキスパート集団 ハードウェアの知見 アルゴリズム実装力 各産業・研究分野の知見 目的の製品に最適なハードウェアを見抜き、 その性能をフル活用するソフトウェアを開 発します。 ハードウェアの特徴と製品要求仕様に合わ せて、アルゴリズムを改良して高速化を実 現します。 開発したい製品に使える技術を見抜き、実 際に動作する実装までトータルにサポート します。 Copyright © Fixstars Group 5

7.

サービス概要 お客様専任のエンジニアが直接ヒアリングを行い、高速化を実現するために乗り越えるべき 課題や問題を明確にしていきます。 高速化のワークフロー お客様 オリジナルソースコードのご提供 高速化したコード コンサルティング 高速化 サポート 先行技術調査 アルゴリズムの改良・開発 レポートやコードへのQ&A 性能評価・ボトルネックの特定 ハードウェアへの最適化 実製品への組込み支援 レポート作成 Copyright © Fixstars Group 6

8.

サービス提供分野 半導体 産業機器 金融 自動車 ● NAND型フラッシュメモリ向け ファームウェア開発 ● 次世代AIチップの開発環境基盤 生命科学 ● Smart Factory実現への支援 ● マシンビジョンシステムの高速化 ● 自動運転の高性能化、実用化 ● ゲノム解析の高速化 ● 次世代パーソナルモビリティの 研究開発 ● 医用画像処理の高速化 Copyright © Fixstars Group ● デリバティブシステムの高速化 ● HFT(アルゴリズムトレード)の高速化 ● AI画像診断システムの研究開発 7

9.

サービス領域 様々な領域でソフトウェア高速化サービスを提供しています。大量データの高速処理は、 お客様の製品競争力の源泉となっています。 暗号アルゴリズム開発 GPU向け高速化 AI・深層学習 画像処理・ アルゴリズム開発 FPGAを活用した システム開発 分散並列システム開発 量子コンピューティング 自動車向け フラッシュメモリ向け ソフトウェア開発 ファームウェア開発 Copyright © Fixstars Group 8

10.

暗号アルゴリズム開発 確かな知見と高速化経験を元に システム開発やアルゴリズム実装をご支援します。 お客様の課題 ご支援内容 高セキュアかつ低遅延な、 コンサルティング 組込システムを開発したい システム設計・開発支援 暗号分野の論文を理解でき、 提案および実装できるエンジニアが欲しい 適切なアクセラレータのご提案 耐量子計算機暗号も組み込んだ、 高パフォーマンスな IP を作りたい アルゴリズムの移植 システムの目標性能を達成させるために、 暗号ライブラリを高速化したい Copyright © Fixstars Group 対象ハードウェアでの高速化 9

11.

本セミナーの構成 1. 会社紹介 2. 暗号のユースケースと実装対象アーキテクチャの関係 3. Intel CPU の AVX-512 命令セットと AVX-512IFMA52 命令サブセット 4. モンゴメリ乗算の有用性 5. モンゴメリ乗算の SIMD 実装例 6. 実装例に対する性能評価 Copyright © Fixstars Group 10

12.

導入:暗号とセキュリティを扱った過去の Tech ブログ 「Fixstars で暗号の高速化?」 Fixstars Tech Blog /proc/cpuinfo ➣ 耐量子公開鍵暗号 CRYSTALS-KYBER の 高速実装(導入編) → アルゴリズム ➣ Intel AVX-512IFMA52 命令セットによる モンゴメリ乗算の高速化 → アーキテクチャ ➣ TrustZone Kinibi の動作概要紹介 → プラットフォーム いずれのトピックでも、同様の案件を受注納品した実績有(開発ではなく、評価調査の場合有) Copyright © Fixstars Group 11

13.

導入:Fixstars と「暗号、セキュリティ」の相性 「セキュリティを確保したい!」 「システム負荷を下げたい!」 より堅牢なアルゴリズムやプラット フォームを使用する代わりにシステ ムを遅くする? セキュリティを緩くして処理を簡単 にする? セキュリティを確保しつつ、高速化す ることでシステム負荷を下げよう! Copyright © Fixstars Group 12

14.

暗号のユースケースと実装対象アーキテクチャの関係 (1) (1) 公開鍵暗号の場合 ユースケース アーキテクチャ 要求 エッジデバイスでの 署名生成、署名検証 ➣ HSM (FPGA 開発を経 て) ➣ CPU + TEE (e.g. Arm TrustZone) ➣ レイテンシの最小化 ➣ TEE で処理する場合は World 間スイッチ回 数を最小化 ➣ サイドチャネル攻撃 (DPA, CPA etc.) 対策 クラウドサーバ上の 署名生成、署名検証 ➣ CPU (e.g. Intel, AMD) ➣ CPU + TEE (e.g. Intel SGX) ➣ 処理あたりに必要な CPU 時間の最小化 理論的な暗号攻撃 ➣ CPU (e.g. Intel, AMD) ➣ GPU (e.g. NVIDIA) ➣ 入手しやすく演算能力が高いアーキテクチ ャを使う ➣ 探索アルゴリズムのスループットの最大化 (注)緑字:Fixstars で、高速化または評価実績があるユースケース×アーキテクチャ Copyright © Fixstars Group 13

15.

暗号のユースケースと実装対象アーキテクチャの関係 (2) (2) 共通鍵暗号の場合 ユースケース アーキテクチャ 要求 通信の暗号化、復号 ➣ 組込(e.g. ルータ) ➣ CPU (e.g. Arm, Intel, AMD) ➣ スループットの最大化 ディスクの暗号化、復号 ➣ CPU (e.g. Arm) ➣ スループットの最大化 (注)緑字:Fixstars で、高速化または評価実績があるユースケース×アーキテクチャ Copyright © Fixstars Group 14

16.

本セミナーの構成 1. 会社紹介 2. 暗号のユースケースと実装対象アーキテクチャの関係 3. Intel CPU の AVX-512 命令セットと AVX-512IFMA52 命令サブセット 4. モンゴメリ乗算の有用性 5. モンゴメリ乗算の SIMD 実装例 6. 実装例に対する性能評価 Copyright © Fixstars Group 15

17.

AVX-512IFMA52 命令サブセットの有用性 「AVX-512IFMA52 はどんな時に有用?」 ➣ 「符号なし多倍長整数」を扱う時 (注)多倍長整数:任意長の整数を、アーキテクチャが扱える数値のビット長 ごとに分割された、配列として表現されたもの。 ➣ 数値の分割数が減少することが高速化につながる時 (e.g. モンゴメリ乗算、どういうことかは後述) Copyright © Fixstars Group 16

18.

AVX-512IFMA52 命令サブセット (図は Intel 公式 intrinsics ガイド から抜粋) Copyright © Fixstars Group 17

19.

AVX-512IFMA52 命令サブセット ➣ 組み込み関数と ニーモニック ともに `madd52` が目印 ➣ コンシューマ向けには Ice Lake で実装 (他に Tiger Lake 等) (図は Intel 公式 intrinsics ガイド から抜粋) Copyright © Fixstars Group 18

20.

本セミナーの構成 1. 会社紹介 2. 暗号のユースケースと実装対象アーキテクチャの関係 3. Intel CPU の AVX-512 命令セットと AVX-512IFMA52 命令サブセット 4. モンゴメリ乗算の有用性 5. モンゴメリ乗算の SIMD 実装例 6. 実装例に対する性能評価 Copyright © Fixstars Group 19

21.

モンゴメリ乗算の有用性 「モンゴメリ乗算はどんな暗号に有用?」 ➣ 𝑧 ≔ 𝑥 ⋅ 𝑦 (mod 𝑝) という演算 = 「整数剰余環上の乗算」を必要とする (実際の暗号では乗法逆元も利用するので、以後「素体上の乗算」として説明) ➣ 法 𝑝 が特殊な性質を持たない (e.g. 𝑝 = 2𝑛 − 1 という形 = メルセンヌ素数の場合は特殊な乗算が可能) Copyright © Fixstars Group 20

22.

今回の取組に関与する暗号方式 ➣ 古典的な公開鍵暗号が最も関与 素体上の乗算の有無 (モンゴメリ乗算が有用) 符号なし多倍長整数を扱う (AVX-512IFMA52 が有用) 古典的な公開鍵暗号 (e.g. RSA ECDSA) 有 有 耐量子計算機公開鍵暗号 (e.g. Kyber Dilithium) 有 無 共通鍵暗号 (e.g. AES) 無 無(バイト列として扱う) 暗号方式 Copyright © Fixstars Group 21

23.

古典的な公開鍵暗号方式における、法のビット長 素体上の乗算を必要とする ⇒ モンゴメリ乗算 法が大きい ⇒ 符号なし多倍長整数として表現 暗号方式 法のビット長の例 備考 RSA 2048(セキュリティビット 112) cf. NIST.SP.800-57pt1r5 Subsection 5.6.1 法は 𝑛 cf. RFC8017 Chapter 5 ECDSA 256(セキュリティビット 128) cf. NIST.SP.800-57pt1r5 Subsection 5.6.1 法は 𝑝 cf. RFC5639 Chapter 2 Copyright © Fixstars Group 22

24.

耐量子計算機公開鍵暗号方式における、法のビット長 (近い未来に関しては…) 素体上の乗算を必要とする ⇒ モンゴメリ乗算 法が小さい ⇒ 多倍長整数として表現する必要はない 暗号方式 法のビット長の例 備考 Kyber 12 (セキュリティビット によらない) 法は 𝑞 = 3329 𝑞 固定、格子次元 𝑘 増加⇒ セキュリティビット増加 cf. Kyber Spec 20210131 Section 1.4 Dilithium 23 (セキュリティビット によらない) 法は 𝑞 = 8380417 𝑞 固定、行列サイズ 𝑘 × ℓ 増加⇒ セキュリティビット増加 cf. Dilithum Spec 20171130 Section 5.3 Copyright © Fixstars Group 23

25.

モンゴメリ演算 𝑋𝑖 = 𝑀𝑅 𝑥𝑖 ⋅ 𝑅2 𝑥0 , 𝑥1 , … 𝑋0 , 𝑋1 , … (複数回の 𝐴𝑟𝑖𝑡ℎ𝑖 ) 𝑍 = 𝐴𝑟𝑖𝑡ℎ(𝑥0 , 𝑥1 , … ) 𝑴𝒐𝒏𝒕𝑨𝒓𝒊𝒕𝒉𝒊 (𝑿, 𝒀) 𝑥 + 𝑦 mod 𝑝 𝑋 + 𝑌 − 𝑝 if 𝑋 + 𝑌 ≥ 𝑝 𝑋 + 𝑌 otherwise 𝑥 − 𝑦 mod 𝑝 𝑋 − 𝑌 if 𝑋 ≥ 𝑌 𝑋 + 𝑌 otherwise 𝑥 ⋅ 𝑦 mod 𝑝 𝑀𝑅(𝑋 ⋅ 𝑌) (複数回の 𝑀𝑜𝑛𝑡𝐴𝑟𝑖𝑡ℎ𝑖 ) 𝑍 = 𝑀𝑜𝑛𝑡𝐴𝑟𝑖𝑡ℎ(𝑋0 , 𝑋1 , … ) 𝑦 = 𝑀𝑅 𝑌 𝑧, 𝑥0 , 𝑥1 , … ∈ ℤ/𝑝ℤ 𝑨𝒓𝒊𝒕𝒉𝒊 (𝒙, 𝒚) モンゴメリ乗算 𝑍, 𝑋0 , 𝑋1 , … ∈ ℤ/𝑝ℤ (Montgomery form) Copyright © Fixstars Group 24

26.

モンゴメリ演算のうち演算量が多い部分 𝑿𝒊 = 𝑴𝑹 𝒙𝒊 ⋅ 𝑹𝟐 𝑥0 , 𝑥1 , … 𝑋0 , 𝑋1 , … (複数回の 𝐴𝑟𝑖𝑡ℎ𝑖 ) 𝑍 = 𝐴𝑟𝑖𝑡ℎ(𝑥0 , 𝑥1 , … ) 𝑴𝒐𝒏𝒕𝑨𝒓𝒊𝒕𝒉𝒊 (𝑿, 𝒀) 𝑥 + 𝑦 mod 𝑝 𝑋 + 𝑌 − 𝑝 if 𝑋 + 𝑌 ≥ 𝑝 𝑋 + 𝑌 otherwise 𝑥 − 𝑦 mod 𝑝 𝑋 − 𝑌 if 𝑋 ≥ 𝑌 𝑋 + 𝑌 otherwise 𝒙 ⋅ 𝒚 𝒎𝒐𝒅 𝒑 𝑴𝑹(𝑿 ⋅ 𝒀) (複数回の 𝑀𝑜𝑛𝑡𝐴𝑟𝑖𝑡ℎ𝑖 ) 𝑍 = 𝑀𝑜𝑛𝑡𝐴𝑟𝑖𝑡ℎ(𝑋0 , 𝑋1 , … ) 赤字:とても演算量が多い 𝒚 = 𝑴𝑹 𝒀 𝑧, 𝑥0 , 𝑥1 , … ∈ ℤ/𝑝ℤ 𝑨𝒓𝒊𝒕𝒉𝒊 (𝒙, 𝒚) 𝑍, 𝑋0 , 𝑋1 , … ∈ ℤ/𝑝ℤ (Montgomery form) Copyright © Fixstars Group 紫字:更にとても演算量が多い 25

27.

モンゴメリ演算の使い方 𝑋𝑖 = 𝑀𝑅 𝑥𝑖 ⋅ 𝑅2 (1) 𝑥0 , 𝑥1 , … 𝑋0 , 𝑋1 , … (複数回の 𝐴𝑟𝑖𝑡ℎ𝑖 ) (複数回の 𝑀𝑜𝑛𝑡𝐴𝑟𝑖𝑡ℎ𝑖 ) (1) 全体の処理の入力値をモンゴメリ表現に変換 (2) 演算が続く間は常にモンゴメリ表現のまま (2) 𝑍 = 𝐴𝑟𝑖𝑡ℎ(𝑥0 , 𝑥1 , … ) 𝑍 = 𝑀𝑜𝑛𝑡𝐴𝑟𝑖𝑡ℎ(𝑋0 , 𝑋1 , … ) (3) 全体の処理の出力値を元の表現に変換 (3) 𝑦 = 𝑀𝑅 𝑌 𝑧, 𝑥0 , 𝑥1 , … ∈ ℤ/𝑝ℤ 𝑍, 𝑋0 , 𝑋1 , … ∈ ℤ/𝑝ℤ (Montgomery form) Copyright © Fixstars Group 26

28.

本セミナーの構成 1. 会社紹介 2. 暗号のユースケースと実装対象アーキテクチャの関係 3. Intel CPU の AVX-512 命令セットと AVX-512IFMA52 命令サブセット 4. モンゴメリ乗算の有用性 5. モンゴメリ乗算の SIMD 実装例 6. 実装例に対する性能評価 Copyright © Fixstars Group 27

29.

採用したモンゴメリ乗算アルゴリズム ➣ [BMSZ13] Algorithm 2 論文では 32-bit SIMD -> radix-232 AVX-512IFMA52 であれば 52-bit SIMD -> radix-252 に変更 [BMSZ13] Joppe W Bos, Peter L Montgomery, Daniel Shumow, and Gregory M Zaverucha. Montgomery multiplication using vector instructions. In Selected Areas in Cryptography–SAC 2013: 20th International Conference, Burnaby, BC, Canada, August 14-16, 2013, Revised Selected Papers 20, pages 471–489. Springer, 2013. Copyright © Fixstars Group 28

30.

採用したモンゴメリ乗算アルゴリズム ➣ [BMSZ13] Algorithm 2 ➣ 固定時間アルゴリズム ➣ 随所で madd を必要とする ➣ mulhi 相当も必要 [BMSZ13] Joppe W Bos, Peter L Montgomery, Daniel Shumow, and Gregory M Zaverucha. Montgomery multiplication using vector instructions. In Selected Areas in Cryptography–SAC 2013: 20th International Conference, Burnaby, BC, Canada, August 14-16, 2013, Revised Selected Papers 20, pages 471–489. Springer, 2013. Copyright © Fixstars Group 29

31.

AVX-512F + AVX-512VL の算術命令 ➣ 扱いたい整数値の bit 長に応じて、使用できる乗算命令が、かなり異なる 「引数となる整数値の bit 長」=「戻り値となる整数値の bit 長」が同じ命令(Intrinsics 表記): 引数となる 整数値の bit 長 add/sub mullo mulhi madd 16-bit *_add_epi16() *_sub_epi16() *_mullo_epi16() *_mulhi_epi16() *_mulhi_epu16() *_madd_epi16() 32-bit *_add_epi32() *_sub_epi32() *_mullo_epi32() N/A N/A 64-bit *_add_epi64() *_sub_epi64() *_mullo_epi64 N/A N/A Copyright © Fixstars Group 30

32.

AVX-512F + AVX-512VL の算術命令 「32-bit × 32-bit = 64-bit の上位 32-bit はどう取得しようか…」 32-bit に対してだけ *_mul_epi32, *_mul_epu32 という少し風変わりな命令がある (例)_mm256_*_mul_ep*32 の場合 奇数番レーンは無視される 7 6 5 4 3 2 1 0 𝑥 32-bit 32-bit 32-bit 32-bit 𝑦 32-bit 32-bit 32-bit 32-bit 𝑧 64-bit 64-bit Copyright © Fixstars Group 64-bit 64-bit 31

33.

AVX-512F + AVX-512VL の算術命令 「加減算は *_add_epi32()/*_sub_epi32() を全レーンに対して使いたい!」 「乗算の *_mul_epi32() で半数ものレーンが無視されるのは困るけど…」 *_shuffle_epi32(…, 0b1011’0001) で偶奇の並べ替えが可能 𝑥𝑒𝑣𝑒𝑛 𝑥𝑜𝑑𝑑 𝑦𝑒𝑣𝑒𝑛 𝑦𝑜𝑑𝑑 𝑧𝑒𝑣𝑒𝑛 𝑧𝑜𝑑𝑑 𝑧𝑒𝑣𝑒𝑛 と 𝑧𝑜𝑑𝑑 が求まり、更に *_add_epi64() 等で演算した後、再び shuffle 命令で上位/下位 32 ビットだけを抽出 Copyright © Fixstars Group 32

34.

AVX-512IFMA52 の乗算命令 ➣ *_madd52hi_epu64, *_madd52lo_epu64 でそれぞれ mul 後の上位/下位 52 ビットが取得可能 (このうちの add の部分に関しては注意が必要だが、疑似コードを読んだ方が一番良いので割愛) ➣ (個人的な感想)32-bit 分割の時より使いやすい 12-bit 分は無視される 3 2 1 0 𝑥 52-bit 52-bit 52-bit 52-bit 𝑦 52-bit 52-bit 52-bit 52-bit 𝑡𝑚𝑝 52-bit 52-bit 52-bit 52-bit Copyright © Fixstars Group 33

35.

本セミナーの構成 1. 会社紹介 2. 暗号のユースケースと実装対象アーキテクチャの関係 3. Intel CPU の AVX-512 命令セットと AVX-512IFMA52 命令サブセット 4. モンゴメリ乗算の有用性 5. モンゴメリ乗算の SIMD 実装例 6. 実装例に対する性能評価 Copyright © Fixstars Group 34

36.

モンゴメリ乗算のスループットの実測値 ➣ とても理想的なプロット (実測値のほとんどが、理論 値の 80% 以上) ➣ tech ブログ の時とは異なる プロット(更にプログラムに改 善を施している + 測定アーキテ クチャが異なる) Copyright © Fixstars Group 35

37.

AVX-512IFMA の使用に伴う理論的な高速化倍率 ➣ 多倍長整数のビット長に応じて、正 確な分割数が異なるため、滑らかでは ないプロットとなる ➣ 100 ビット - 200 ビットでは 2-3 倍 ⇒ ECDLP は約 2-3 倍速くなる ➣ 最終的には 2.84 倍に収束 ⇒ RSA は約 2.8 倍速くなる Copyright © Fixstars Group 36

38.

(補足)Number Theoretic Library について ➣ 数論研究者の間では有名である模様。 ➣ 素体上の乗算の処理は最終的に除算 を呼び出していた ⇒ 結局モンゴメリ乗 算を使っていない? cf. ZZ_p 型に対する mul() → _ntl_gmulmod() → _ntl_mpn_tdiv_qr() (図は https://libntl.org/ より、本実験でも v11.5.1 を使用) Copyright © Fixstars Group 37

39.

モンゴメリ乗算のスループットの見積 実装 サイクル数(N は分割数) AVX-512F + AVX-512VL 組込関数のみを用いた実装 (ベクトル長 256-bit) 実装方針の違い ➣ 32-bit × 32-bit = 64-bit 向けの mulhi, mullo がない ⇒ mul 命令と shuffle 命令と組み合 わせて演算 ➣ 52-bit × 52-bit = 104-bit 向けの mulhi, mullo がある ➣ AVX-512F + AVX-512VL の場合 以上に演算命令をストールさせない工 夫が必要 AVX-512IFMA52 組込関数 を用いた実装 (ベクトル長 256-bit) 一見すると係数に大きな違いがないが、 分割数が大きく変化するため、 実際はサイクル数が Copyright © Fixstars Group 13/12 28/24 ⋅ 1/52 2 1/32 = 1 𝟐.𝟖𝟒𝟑𝟕𝟓 倍程度となる 38

40.

(補足)AVX-512F + AVX-512VL のみを用いた実装 ➣ 使用した算術命令のスループットを調べ、回数を全て数える ➣ ベクトル長 256-bit でモンゴメリ乗算 8 回分をベクトル化した場合の内訳: モンゴメリ乗算 1 回 あたり合計サイクル数 Copyright © Fixstars Group 39

41.

(補足)AVX-512IFMA52 を併用した実装 ➣ 使用した算術命令のスループットを調べ、回数を全て数える ➣ ベクトル長 256-bit でモンゴメリ乗算 4 回分をベクトル化した場合の内訳: モンゴメリ乗算 1 回 あたり合計サイクル数 Copyright © Fixstars Group 40

42.

(補足)スループットの見積方針 「実装したアルゴリズムが演算律速であることを仮定した時、 1 回あたりの処理に必要な合計 CPU サイクル数を知りたい!」 (2) 算術演算命令の回数 (1) 命令のスループット ➣ Intel 公式 intrinsics ガイド ➣ Agner Fog 先生による PDF 化されている情報 ➣ uops.info が公開しているフ ィルタリング可能なリスト ➣ ➣ program .cpp a.out Copyright © Fixstars Group objdump -d 41

43.

(補足)命令のスループット参考資料 (1) ➣ Intel 公式 intrinsics ガイド Pros: ・公式情報である ・どのニーモニックに相当するか、 もすぐに見れる Cons: ・全てのマイクロアーキテクチャの 場合について事細かに書かれている わけではない(Skylake, Icelake 等、 変更が多いマイクロアーキテクチャ は書かれていることが多い) (図は _mm256_madd52hi_epu64 の場合から抜粋) Copyright © Fixstars Group 42

44.

(補足)命令のスループット参考資料 (2) ➣ Agner Fog 先生による PDF 化されている情報 Pros: ・各アーキテクチャごとに表形式で まとまっている Cons: ・実測値であるため、プロセッサベ ンダからの情報と相違がある場合有 ・命令によっては、ベクトル長を分 けて書いていないことに伴い、スル ープット表記が一つの値になってい ない (図は Ice Lake, Tiger Lake の場合から抜粋) Copyright © Fixstars Group 43

45.

(補足)命令のスループット参考資料 (3) ➣ uops.info が公開しているフ ィルタリング可能なリスト Pros: ・フィルタリング可能 ・データが膨大 Cons: ・実測値であるため、プロセッサベン ダからの情報と相違がある場合有 (図は Tiger Lake, vpmadd52huq の場合から抜粋) Copyright © Fixstars Group 44

46.

(補足)算術演算命令の回数の調査方法 ➣ ソースコードを静的解析 ➣ バイナリを解析 ・記述されている組込関数等の回数を数える ・静的解析 = 記述されているニーモニック 等の回数を数える ・動的解析 = Valgrind with Callgrind Pros: ・手軽 ・ループ回数に応じた一般式が導ける Pros: ・正確 Cons: ・最適化によって、実際のバイナリで実行され る命令回数は異なることが多い program .cpp Cons: ・静的解析は非常に労力がかかる ・Valgrind は AVX512 をサポートしきれ ていない objdump -d a.out Copyright © Fixstars Group 45

47.

(補足)スループットの見積方法 (2) 算術演算命令の回数 (1) 命令のスループット ➣ Intel 公式 intrinsics ガイド ➣ ➣ Agner Fog 先生による PDF 化されている情報 ➣ uops.info が公開しているフ ィルタリング可能なリスト ➣ program .cpp a.out 念のため全てチェックして総合的に判断 Copyright © Fixstars Group objdump -d ソースコードの静的解析のみ 46

48.

(補足)スループットの見積に際して考慮しない事項 <考慮する事項> <考慮しない事項> (1) 命令のスループット (1) 命令のレイテンシ (2) 算術演算命令の回数 (2) メモリ命令の回数 理由( tech ブログ より): 演算律速を仮定した場合 Copyright © Fixstars Group 47

49.

参考資料・リンク集 ➣ 論文、スペック論文 ・ [BMSZ13] Joppe W Bos, Peter L Montgomery, Daniel Shumow, and Gregory M Zaverucha. Montgomery multiplication using vector instructions ・Kyber Spec 20210131 ➣ Fixstars Tech Blog /proc/cpuinfo ・耐量子公開鍵暗号 CRYSTALS-KYBER の高速実装(導入編) ・Intel AVX-512IFMA52 命令セットによるモンゴメリ乗算の高速化 ・TrustZone Kinibi の動作概要紹介 ・Dilithum Spec 20171130 ➣ 仕様書、報告書 ➣ その他 ・RFC8017 (RSA) ・ Intel 公式 intrinsics ガイド ・RFC5639 (ECDSA) ・ Agner Fog 先生による PDF 化されている情報 ・NIST.SP.800-57pt1r5 (Key Management) ・ uops.info が公開しているフィルタリング可能なリスト ・ Number Theoretic Library Copyright © Fixstars Group 48

50.

Thank you! お問い合わせ窓口 : [email protected] Copyright © Fixstars Group 49