論文の概要: Cut Tracing with E-Graphs for Boolean FHE Circuit Synthesis
- arxiv url: http://arxiv.org/abs/2506.12883v1
- Date: Sun, 15 Jun 2025 15:27:51 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-17 17:28:47.084596
- Title: Cut Tracing with E-Graphs for Boolean FHE Circuit Synthesis
- Title（参考訳）: ブールFHE回路合成のためのEグラフによるカットトレーシング
- Authors: Julien de Castelnau, Mingfei Yu, Giovanni De Micheli,
- Abstract要約: ホモモルフィック暗号化(英: Homomorphic Encryption, FHE)は、暗号化されたデータに対するセキュアな計算を可能にする、有望なプライバシ保護技術である。
既存の作業は主にFHE回路の乗算深度(MD)と乗算複雑性(MC)をターゲットにしている。
カットトレーシングが2つの最先端MCとMDのリダクションフローを効果的に組み合わせ、その弱点をバランスさせてランタイムを最小化する方法を示す。
- 参考スコア（独自算出の注目度）: 1.9204566034368082
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Fully Homomorphic Encryption (FHE) is a promising privacy-preserving technology enabling secure computation over encrypted data. A major limitation of current FHE schemes is their high runtime overhead. As a result, automatic optimization of circuits describing FHE computation has garnered significant attention in the logic synthesis community. Existing works primarily target the multiplicative depth (MD) and multiplicative complexity (MC) of FHE circuits, corresponding to the total number of multiplications and maximum number of multiplications in a path from primary input to output, respectively. In many FHE schemes, these metrics are the primary contributors to the homomorphic evaluation runtime of a circuit. However, oftentimes they are opposed: reducing either depth or complexity may result in an increase in the other. To our knowledge, existing works have yet to optimize FHE circuits for overall runtime, only considering one metric at a time and thus making significant tradeoffs. In this paper, we use e-graphs to augment existing flows that individually optimize MC and MD, in a technique called cut tracing. We show how cut tracing can effectively combine two state-of-the-art MC and MD reduction flows and balance their weaknesses to minimize runtime. Our preliminary results demonstrate that cut tracing yields up to a 40% improvement in homomorphic evaluation runtime when applied to these two flows.
- Abstract（参考訳）: FHE(Fully Homomorphic Encryption)は、暗号化されたデータに対するセキュアな計算を可能にする、将来性のあるプライバシ保護技術である。
現在のFHEスキームの最大の制限は、実行時のオーバーヘッドが高いことである。
その結果、FHE計算を記述した回路の自動最適化は、論理合成コミュニティにおいて大きな注目を集めている。
既存の研究は主にFHE回路の乗算深さ(MD)と乗算複雑性(MC)をターゲットにしており、それぞれ一次入力から出力までの経路における乗算の総数と最大乗算数に対応する。
多くのFHEスキームにおいて、これらのメトリクスは回路の準同型評価ランタイムの主要な貢献者である。
しかし、しばしばそれらが反対される: 深さや複雑さを減らせば、もう一方が増加する可能性がある。
我々の知る限り、既存の研究はまだFHE回路をランタイム全体向けに最適化していない。
本稿では,カットトレーシングと呼ばれる手法を用いて,MCとMDを個別に最適化する既存のフローを拡大するために電子グラフを用いる。
カットトレーシングが2つの最先端MCとMDのリダクションフローを効果的に組み合わせ、その弱点をバランスさせてランタイムを最小化する方法を示す。
この2つの流れに適用した場合, カットトレーシングは相同性評価の実行時間において最大40%改善することを示した。
関連論文リスト
- Scaling Probabilistic Circuits via Monarch Matrices [109.65822339230853]
確率回路(PC)は確率分布の抽出可能な表現である。
そこで本研究では,PCの和ブロックに対する新しいスパースパラメータと構造化パラメータ化を提案する。
論文 参考訳（メタデータ） (2025-06-14T07:39:15Z) - Fast correlated decoding of transversal logical algorithms [67.01652927671279]
大規模計算には量子エラー補正(QEC)が必要であるが、かなりのリソースオーバーヘッドが発生する。
近年の進歩により、論理ゲートからなるアルゴリズムにおいて論理キュービットを共同で復号化することにより、症候群抽出ラウンドの数を削減できることが示されている。
ここでは、回路を介して伝播する関連する論理演算子製品を直接復号することで、回路の復号化の問題を修正する。
論文 参考訳（メタデータ） (2025-05-19T18:00:00Z) - Finding Transformer Circuits with Edge Pruning [71.12127707678961]
自動回路発見の効率的かつスケーラブルなソリューションとしてエッジプルーニングを提案する。
本手法は,従来の手法に比べてエッジ数の半分未満のGPT-2の回路を探索する。
その効率のおかげで、Edge PruningをCodeLlama-13Bにスケールしました。
論文 参考訳（メタデータ） (2024-06-24T16:40:54Z) - Parallel Decoding via Hidden Transfer for Lossless Large Language Model Acceleration [54.897493351694195]
本稿では,複数連続するトークンを1つのフォワードパスで同時に復号する,新しい並列復号法,すなわちthithidden Transferを提案する。
加速度測定では,Medusa や Self-Speculative decoding など,単モデル加速技術よりも優れています。
論文 参考訳（メタデータ） (2024-04-18T09:17:06Z) - Accelerating Matrix Factorization by Dynamic Pruning for Fast Recommendation [0.49399484784577985]
MF(Matrix Factorization)は、リコメンデーションシステム(RS)のための協調フィルタリングアルゴリズムである。
現在のRSではユーザ/イテムが劇的に増加しているため、MFモデルのトレーニングに要する計算の複雑さは大幅に増大している。
我々は、追加の計算資源を誘導することなく、MFを高速化するアルゴリズム手法を提案する。
論文 参考訳（メタデータ） (2024-03-18T16:27:33Z) - ReLU and Addition-based Gated RNN [1.484528358552186]
従来のリカレントゲートの乗算とシグモイド関数を加算とReLUアクティベーションで置き換える。
このメカニズムは、シーケンス処理のための長期メモリを維持するために設計されているが、計算コストは削減されている。
論文 参考訳（メタデータ） (2023-08-10T15:18:16Z) - Towards Model-Size Agnostic, Compute-Free, Memorization-based Inference
of Deep Learning [5.41530201129053]
本稿では,新しい暗記ベース推論(MBI)を提案する。
具体的には、リカレント・アテンション・モデル(RAM)の推論機構に着目します。
低次元のスリープ性を活用することで、我々の推論手順は、スリープ位置、パッチベクトルなどからなるキー値対をテーブルに格納する。
計算は、テーブルを利用してキーと値のペアを読み出し、暗記による計算自由推論を実行することにより、推論中に妨げられる。
論文 参考訳（メタデータ） (2023-07-14T21:01:59Z) - Optimal qubit assignment and routing via integer programming [0.22940141855172028]
論理量子回路を2ビット接続に制限のあるハードウェアにマッピングする問題を考察する。
我々はこの問題を2変数のネットワークフロー定式化を用いて整数線形プログラムとしてモデル化する。
本稿では,回路の忠実度,全深度,クロストークの尺度などのコスト関数について考察する。
論文 参考訳（メタデータ） (2021-06-11T15:02:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。