CPU/GPU高速化セミナー～暗号アルゴリズムの高速化～（2024/05/27）

5.2K Views

June 03, 24

#cpu #gpu #cpu高速化 #gpu高速化 #暗号 #アルゴリズム #モンゴメリ乗算 #intel #cpugpu高速化 #高速化シリーズ #暗号アルゴリズム #高速化 #AVX-512 #SIMD

スライド概要

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

本セミナーでは、暗号アルゴリズムで頻出するモンゴメリ乗算について、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

株式会社フィックスターズ

@fixstars

スライド一覧

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

またはPlayer版

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

（ダウンロード不可）

関連スライド

Kaggleスコアアップセミナー～画像系コンペ入門[前編]（2023/08/02）

kaggle 画像処理機械学習深層学習ディープラーニングコンペ初心者 kaggleスコアアップシリーズ

株式会社フィックスターズ 63.5K

いまさら聞けない ARM を使ったNEONの基礎と活用事例（2021/08/05）

arm neon

株式会社フィックスターズ 38.6K

ROS2自律走行実現に向けて 2 ～次世代ロボット開発フレームワークROS2のビルドシステム徹底理解～（2022/11/30）

ros2 gpu ロボット自律走行 ros2シリーズ高速化シリーズ

株式会社フィックスターズ 30.6K

Kaggleスコアアップセミナー～画像系コンペ入門[後編]（2023/09/26）

kaggle 画像処理機械学習ディープラーニングコンペ初心者 kaggleスコアアップシリーズ

株式会社フィックスターズ 29.9K

いまさら聞けない！CUDA高速化入門～プログラミングモデルとアーキテクチャの解説、高速化の実践～（2021/10/29）

cuda gpu cuda高速化高速化シリーズ

株式会社フィックスターズ 28.9K

CUDA高速化セミナー vol.2 ～CUDAアーキテクチャの進化～（2022/06/23）

gpu cuda cuda高速化高速化シリーズ cuda高速化シリーズ

株式会社フィックスターズ 27K

各ページのテキスト

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

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

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

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

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

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

10.

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

11.

12.

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

13.

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.

17.

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

18.

https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html

19.

https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html

20.

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.

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

https://eprint.iacr.org/2013/519.pdf

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

https://eprint.iacr.org/2013/519.pdf

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.

36.

https://proc-cpuinfo.fixstars.com/2024/01/intel_avx-512ifma52/

37.

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.

41.

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

https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html

44.

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

https://www.agner.org/optimize/instruction_tables.pdf

45.

https://uops.info/table.html

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.

https://proc-cpuinfo.fixstars.com/2024/01/intel_avx-512ifma52/

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.

CPU/GPU高速化セミナー ～暗号アルゴリズムの高速化～（2024/05/27）